그리디 (탐욕법)

그리디(Greedy) 알고리즘은 말 그대로 눈 앞의 가장 큰 이익을 추구하는 기법이다.

최적의 해를 얻기 위해 발생하는 각각의 선택지 중, 그 순간에 최적이라고 생각하는 선택지를 고르는 알고리즘이며 단순한만큼 실행 시간이 빠르다.

그러나 일반적으로 생각했을 때 눈 앞의 가장 큰 이익을 선택하는 것이 최종적으로 최적의 선택이라고는 할 수 없다.

다음의 상황에서 목적지에 도달하기 위한 가장 빠른 시간을 구해보자.

그리디 알고리즘을 사용하면 다음과 같고, 총 35분이 소요된다.

그러나 실제 가장 빠른 시간이 걸리는 방법은 다음과 같고, 총 30분이 소요된다.

정리해보면 그리디 알고리즘은 특정 상황 즉, 그리디를 사용한 방법이 정답이라는 보장이 되어야 사용할 수 있다.

예시

동전 개수 구하기

500원, 100원, 10원 동전이 무수히 많다고 가정할 때 가장 적은 수의 동전을 이용해 1230원을 만들었을 때 동전의 개수는 몇개인가?

500원, 100원, 10원의 순서로 사용할 수 있는 한도까지 사용하면 답을 구할 수 있다.

#include <iostream>
#include <vector>

int main() 
{
	int Total = 1230;
	std::vector<std::pair<int, int>> Coins = { { 500, 0 }, { 100, 0 }, { 10, 0 } };

	for (auto& Coin : Coins)
	{
		while (Coin.first <= Total)
		{
			Total -= Coin.first;
			++Coin.second;
		}
	}

	std::cout << "500원 개수 : " << Coins[0].second;
	std::cout << "\\n100원 개수 : " << Coins[1].second;
	std::cout << "\\n10원 개수 : " << Coins[2].second;
	std::cout << "\\n총 개수 : " << Coins[0].second + Coins[1].second + Coins[2].second;

	return 0;
}

500원 개수 : 2
100원 개수 : 2
10원 개수 : 3
총 개수 : 7

이 문제에 그리디 알고리즘을 사용할 수 있는 이유는 작은 액수의 동전이 큰 액수 동전의 약수이기 때문이다.

즉, 100원을 통해 500원을 만들 수 있고, 10원을 통해 100원, 500원을 만들 수 있기 때문에 그리디 알고리즘을 사용할 수 있다.