알고리즘 3강. 탐욕 알고리즘(Greedy Algorithm)

[탐욕 알고리즘 강좌]

매 순간마다 최선의 선택!

탐욕 알고리즘(Greedy Algorithm)

---

오늘 알아볼 알고리즘은 '탐욕 알고리즘(Greedy Algorithm)' 입니다. 알고리즘의 이름 그대로, 상당히 욕심이 많은 알고리즘 입니다. 탐욕 알고리즘이 어떤 알고리즘이냐면, 매 순간마다 최선의 선택을 하는 녀석입니다. 즉, 선택할때마다 가장 좋다고 생각되는 것을 선택해나가며 최종적인 해답을 구하는 알고리즘이라고 말할 수 있습니다. 그러나, 이 알고리즘을 설계할 때 유의할 점은 전체를 고려하는게 아니라 문제를 부분적으로 나누어, 나누어진 문제에 대한 최적의 해답을 구하므로 전체적인 최적의 해가 될 수 있는 경우가 존재합니다. 한번 예를 보아볼까요?

탐욕 알고리즘의 대표적인 문제로 거스름돈을 계산하는 문제가 있는데, 만약 거스름돈을 줄때는 최소의 동전 수로 거슬러 주며, 동전은 1원, 7원, 10원짜리의 동전이 있다고 가정합니다. 그리고 손님에게 14원을 거슬러 주어야 한다고 생각해봅시다. 이 문제를 탐욕 알고리즘으로 풀게되면, 매 순간마다 최선의 선택을 하려고 하기 때문에 10원, 1원, 1원, 1원, 1원으로 총 5개의 동전을 써서 손님에게 거스름돈을 건네줄 수 있을 것입니다.

그러나, 사실은 7원짜리 동전 2개로 거슬러 주게된다면 동전 2개를 사용해 건네주어서 최소의 동전 수로 거스름돈을 건네줄 수 있게 됩니다. 이제야 아실 것 같으신가요? 왜 탐욕 알고리즘이라고 불리냐면, 미래를 보지 않고 바로 앞에있는 것만 바라보기 때문에 붙여진 이름입니다. 한번 심심삼아 이 문제를 코드로 해결해보도록 합시다.

#include <stdio.h>

int coin[3] = {10, 7, 1};
int count[3];

int main()
{
	int m, i = 0, f = 0;

	scanf("%d", &m);
	while (i < 3)
	{
		if (coin[i] > m)
			i++;
		else if (coin[i] < m)
		{
			m -= coin[i];
			count[i]++;
		}
		else
		{
			f = 1;
			count[i]++;
			break;
		}
	}

	if (f)
		printf("%d원 동전은 %d개, %d원 동전은, %d개, %d원 동전은 %d개입니다.\n", 
				coin[0], count[0], coin[1], count[1], coin[2], count[2]);
	else
		printf("해답을 구할 수 없습니다.\n");

	return 0;
}

결과:

14
10원 동전은 1개, 7원 동전은, 0개, 1원 동전은 4개입니다.
계속하려면 아무 키나 누르십시오 . . .

위의 코드에서는 큰 단위의 동전부터 거슬러 주고 있으며, 선택한 동전이 남은 돈보다 크다면 다른 동전을 택하고, 작다면 선택한 동전을 남은 돈에서 빼고 사용한 동전의 갯수를 증가시킵니다. 마지막으로 같다면 사용한 동전의 갯수를 증가시키고, 반복문을 빠져 나옵니다. 이번에는 아래와 같이 7원 단위의 동전을 5원 단위의 동전으로 바꾸고, 아무런 숫자 하나를 입력해보세요.

int coin[3] = {10, 5, 1};

저 같은 경우는 19를 입력해 보았습니다. 그랬더니 아래와 같은 결과가 나타났습니다.

결과:

19
10원 동전은 1개, 5원 동전은, 1개, 1원 동전은 4개입니다.
계속하려면 아무 키나 누르십시오 . . .

이 경우에는 전체적인 최적의 해답과 같습니다. 최소 6개의 동전으로 돈을 거슬러 줄 수 있게된 셈입니다. 이 탐욕 알고리즘으로 거스름돈 교환 문제를 풀게 된다면, 큰 단위의 동전이 작은 단위의 동전의 배수가 되어야 탐욕 알고리즘을 적용할 수 있습니다. 위 같은 경우는, 10원 동전은 1과 5의 배수이고, 5는 1의 배수이므로 탐욕 알고리즘을 적용할 수 있었던 것입니다. 유의하셔야 할 점은 매 순간마다 최선의 선택을 하여 나온 해가 반드시 전체적인 최적해는 아니라는 것입니다. 그렇기 때문에, 탐욕 알고리즘을 사용할 때에는 전체적인 최적해 인지를 항상 염두해 두실 필요가 있습니다. 즉, 탐욕 알고리즘을 사용하시기 전에 탐욕 알고리즘을 사용해도 되는지 검증 단계를 거치시는게 좋습니다.

이 탐욕 알고리즘은 상당히 여러 곳에서 응용되고 있으며, 유명한 다익스트라의 최단 경로 알고리즘이나 최소 비용 신장 트리 혹은 배낭 채우기 문제 등에서 이용하고 있는 알고리즘입니다. 탐욕 알고리즘에 어느정도 익숙해지고 싶다거나, 더 자세히 알고싶으신 분들은 위에서 말한 배낭 채우기 문제나 최단 경로 알고리즘 등에 관련된 문제를 풀어보시길 권합니다. 모두 수고하셨고, 여기까지 읽어주셔서 모두에게 감사드립니다.

다음 알고리즘 강좌에는 백트래킹(Backtracking)을 다룰 예정입니다. 참고하세요!