탐욕 알고리즘(Greedy algorithm)

 

매 순간마다 최적의 해를 찾는 문제해결 패러다임 이다.

 

 

 

 

알고리즘의 작동 방식이 이름과 매우 흡사하다.

 

 

 

 

간단하게 예를 하나 들어보자.

 

탐욕 알고리즘을 이용하는 대표적인 문제는 동전 거스름돈 문제이다.

 

이 문제는 거슬러 받는 동전의 개수를 가장 적게 받아야 하는 문제이다.

 

 

 

 

 

동전의 종류는 현실과 마찬가지로 1원, 10원, 50원, 100원, 500원이 있다고 하고

 

거슬러 받아야 할 돈은 총 1761원이라고 하자.

 

 

생각하기 가장 쉬운 방법은, 액수가 가장 큰 동전부터 채워서 주는 것이다.

 

이렇게 줄 경우

500원 3개  +  100원 2개  +  50원 1개  +  10원 1개  +  1원 1개  ==>>  총 8개의 동전을 주게 된다.

 

 

과연 최소한의 개수로 동전을 준 것이 맞을까?   질문의 답은 '예' 다.

 

 

다만, 동전 거스름돈 문제에서 탐욕 알고리즘을 사용하기 위해서는 조건이 하나 있다.

모든 동전은 서로 약수와 배수 관계여야 한다.

 

만약 그렇지 않다면, 우리는 동적 계획법을 사용해야 할 것이다.

 

 

다시 본론으로 돌아와서, 어떻게 해야 8개를 주는 방법이 나온 것일까?

 

 

내용은 굉장히 간단하다.

 

현재 거스름돈에서 가장 큰 액면가의 동전을 나눈 후에, 그 값이 0보다 클 경우

현재 거스름돈  =  이전의 거스름돈  -  ( 해당 액면가의 동전  X  나눈 후 나온 몫 ) 이 된다.

 

위의 과정을 계속 반복해주면 된다.

 

 

숫자를 대입하여 설명하면

 

ㄱ. 1761원에서 가장 큰 액면가인 500으로 나눈다.  ==>>  몫  :  3 (500원짜리 3개 사용)

ㄴ. 현재 거스름돈  =  1761  -  ( 500  X  3 )  =  261 이 된다.

 

다시,

 

ㄱ. 261에서 그 다음으로 큰 액면가인 100으로 나눈다.  ==>>  몫  :  2 (100원짜리 2개 사용)

ㄴ. 현재 거스름돈  =  261  -  ( 100  X  2 )  =  61 이 된다.

 

                                                  .

                                                  .

                                                  .

 

위의 과정을 더이상 진행할 수 없을 때까지 반복한 후 나온 값이 최종 해이다.

 

 

 

 

 

그런데 탐욕 알고리즘을 적용하기 전에 주의해야 할 점이 있다.

 

탐욕 알고리즘을 적용하려면 매 순간의 최적해가 문제에 대한 최적해를 의미해야 한다.

 

즉, 매 순간에 나온 해가 다음 순간의 해와 무관해야 한다.

 

그렇기 때문에 탐욕 알고리즘은 최적해를 보장하지 못할 수도 있다.

 

그렇기에 근사값을 찾기 위한 알고리즘으로 사용될 수 있다.