Greedy Algorithm

개요

그리디 알고리즘이란, 주어진 상황에서 가장 좋은 것을 고르는 문제 해결 방법이다.

종종 그리디 알고리즘의 “Greedy”를 그대로 번역하여 이를 “탐욕적 알고리즘”이라고 부르기도 한다.

 

예시

바로 예시를 간단하게 들어보자.

 

거스름돈 문제

거스름돈 문제는 그리디 알고리즘을 설명할 때, 가장 대표적으로 나오는 예시이다.

 

재훈이가 마트에서 3640원짜리 물건을 사며 5000원권 한 장을 냈다.
재훈이에게 동전으로 거스름돈을 지불하고자 할 때, 거스름돈을 지불할 수 있는 동전의 최소 개수를 구해라.
거스름돈으로 줄 수 있는 동전의 종류는 500원, 100원, 50원, 10원으로 총 4가지이다.

 

그리디 알고리즘을 이 문제에 적용하려면 어떻게 해야할까?

 

바로 가장 큰 단위부터 차례대로 돈을 거슬러 주면 된다.

1. 총 지불해야할 거스름돈의 금액은 5000-340원으로 총 1360원이다.
2. 가장 큰 단위인 500원짜리 동전을 먼저 사용하면, 1360-(500*2) = 360원이 남는다.
3. 그 다음으로 100원짜리 동전을 사용하면, 360-(100*3) = 60원이 남는다.
4. 그 다음으로 50원짜리 동전을 사용하면, 60-50 = 10원이 남게된다.
5. 마지막으로 10원짜리 동전 1개를 사용하면 거스름돈을 모두 지불하게 된다.
6. 따라서 거스름돈을 지불할 수 있는 동전의 최소 개수는 2+3+1+1개로 총 7개가 된다.

우리는 이와 같은 방법으로 거스름돈 문제를 해결 할 수 있다.

 

그리디 알고리즘이 적용되지 않는 경우

여기서, 다음과 같은 의문이 들 수도 있다.

❓가장 큰 동전부터 주는 방법이 항상 최선의 방법일까?

결론부터 말하자면 그렇지 않을 수도 있다.

 

이는 그리디 알고리즘이 한정적인 경우에 한해 적용된다는 사실을 알려준다.

다음의 예시로 그리디 알고리즘이 적용되지 않는 경우를 알아보자.

 

거스름돈 800원을 지불하고자 할 때, 가장 적은 동전의 개수를 사용하여 거스름돈을 지불하시오.
사용 가능한 동전의 종류는 500원, 400원, 100원짜리가 있다.

 

이 문제에 그리디 알고리즘을 적용해보면, 500원 1개와 100원 3개를 이용한 4개라는 답을 얻을 수 있다.

그러나, 이 문제는 400원짜리 2개를 지불하여 해결하는 것이 올바른 답이다.

 

그렇다면, 왜 위와 같은 경우에는 그리디 알고리즘을 적용할 수 없는 것일까?

 

그 이유는 그리디 알고리즘은 “큰 단위가 항상 작은단위의 배수일 때”에만 적용이 가능하기 때문이다.

 

위의 문제에서는 500원짜리 동전과 400원짜리 동전은 배수의 관계가 아니기 때문에, 그리디 알고리즘을 적용하는 것은 좋은 방법이 아님을 알 수 있다.