[Algorithm] 그리디 알고리즘 - 거스름돈 문제(C++)

www.youtube.com/watch?v=PNPIk3hc6ic

 

그리디(Greedy) 알고리즘

그리디 알고리즘: 당장 눈 앞에 뵈는 최적의 상황을 쫓는 알고리즘, 단순한 형태이다.

• 장점: 최적의 해에 근사한 값을 빠르게 구할 수 있다.
• 정렬기법이 함께 이용

그리디 알고리즘이 최적의 해를 보장하는 경우도 있지만 그렇지 않은 경우도 많다. 그럴 경우에는 다이나믹 프로그래밍 등의 기타 알고리즘 기법을 적용하여 해결해야한다.

 

문제설명 & 풀이

문제: 1260원을 거슬러주어야 할 때 가장 적은 숫자의 화폐를 이용해 거슬러주는 경우에 대해서 찾아본다.

풀이

• 가장 큰 동전 먼저 계산을 해준다.
• 그리디 알고리즘이란? 큰 경우부터 찾는 알고리즘과 같이 간단하게 탐욕적으로(한가지 경우만 보고 쫓는다) 문제를 해결하는 기법을 말한다.

 

ScreenShot

 

Code

#include <iostream>

int main() {
	std::cout << "Greedy Algorithm\n";
	int num = 1260;
	int result = 0;
	result += num / 500;
	num = num % 500;

	result += num / 100;
	num = num % 100;

	result += num / 50;
	num = num % 50;

	result += num / 10;
	num = num % 10;
	std::cout << "result: " << result;
}