[알고리즘] 그리디 알고리즘

그리디 알고리즘(Greedy Algorithms)은 이름 그대로 번역하면 '탐욕법'이라고 해석됩니다. 이 이름 그대로, 어떤 문제에 대해서 탐욕적으로 문제를 푸는 방법이 바로 이 그리디 알고리즘입니다. 탐욕적이라는 말을 조금 더 듣기 좋게 풀어보자면, '현재 상황에서 최선의 선택을 하는 방법'이라고 할 수 있습니다. 즉, 매 순간 여러 선택지 중 가장 좋아 보이는 선택지를 고르고, 이 선택이 추후에 미칠 영향은 고려하지 않습니다.

 

추후에 미칠 영향을 고려하지 않는다는 말은, 결과적으로는 최적의 해가 아닐 수도 있다는 것을 뜻합니다. 그래서 항상 어떤 문제와 마주치면, 이 문제를 그리디를 이용해 풀어도 되는 것인지에 대해 생각을 해 보아야 합니다. 하지만 만일 그리디로 접근해도 되는 문제라면, 그리디를 사용하는 것이 가장 효과적이고 쉽습니다.

 

 

 

그리디 알고리즘을 사용하는 가장 대표적인 예시가 바로 거스름돈 문제입니다.

 

거스름돈으로는 500원, 100원, 50원, 10원짜리 동전만을 사용하고, 각 동전들은 무한하게 존재합니다. 손님에게 N원을 거슬러주어야 할 때, 거슬러주어야 할 동전의 최소 개수를 구하는 문제입니다. 단, 거슬러 주어야 할 N원은 항상 10의 배수입니다.

 

이 문제를 그리디를 이용해 접근하면, N원을 거슬러주어야 할 때, 거슬러 주는 동전의 수를 최소화해야 하기 때문에, 가능한 한 가장 큰 단위의 동전을 먼저 거슬러주는 것이 바람직합니다. 그래서 거슬러 주어야 할 돈 보다 더 큰 금액의 동전을 제외한 동전 중에 가장 큰 단위의 동전부터 차례로 거슬러 주면 되는 것입니다. 

 

예를 들어 설명하면, 1370원을 거슬러주어야 한다면, 먼저 가장 큰 금액의 동전인 500원을 거슬러 줄 수 있는 대로 2개를 거슬러주고, 남은 돈인 370원을 500원을 제외하면 가장 큰 단위인 100원으로 3개 거슬러주고, 그 뒤에 50원, 10원 순서로 거슬러주면 되는 것입니다.

 

 

 

Java를 이용한 코드를 살펴보겠습니다.

 

int N = 1370;
int[] coins = {500,100,50,10};
int cnt = 0;
int i;
 
for(i=0;i<4;i++)
{
    cnt += N / coins[i];
    N = N % coins[i];
}
 
System.out.println(cnt);

N이 1370원일 때, 정답은 8입니다. 500원 2개, 100원 3개, 50원 1개, 10원 2개를 이용하면 최소 개수의 동전으로 거스름돈을 구성할 수 있습니다.

 

N원을 거스름돈의 종류, 즉 처음에는 500원, 그 다음에는 100원...으로 나누어주면, 그 몫이 해당 동전을 몇 개 까지 거슬러 줄 수 있는지를 나타내고, 나머지가 해당 동전을 걸러주고 남은 금액을 의미합니다. 

 

따라서 동전의 개수를 새는 cnt 변수에는 몫을 계속 더해주고, 원래의 금액 N은 나머지로 반복문을 돌 때마다 최신화를 해주면, 최종적으로 사용되는 동전의 개수를 파악할 수 있습니다.

 

 

하지만, 이 방법은 위의 동전의 종류들이 서로가 서로의 배수와 약수 관계에 있기 때문에 가능합니다. 무슨 말이냐 하면, 500은 100, 50, 10의 배수이고, 100은 50, 10의 배수, 50은 10의 배수라는 뜻입니다. 이러한 특수한 관계이기 때문에 그리디 알고리즘을 적용할 수 있는 것입니다.

 

만일 500원, 300원, 50원짜리 동전만 존재하는 나라에서 같은 문제를 푼다면, 600원을 거슬러 주어야 할 때, 그리디 알고리즘을 사용하면 500원 동전 한 개와 50원 동전 두 개를 거슬러 주게 됩니다. 하지만 실제로 사용하는 동전을 최소화하려면, 300원 동전 두 개를 거슬러 주는 것이 가장 최적의 해가 됩니다. 이러한 경우에는 다이나믹 프로그래밍 등의 다른 방법을 찾아보아야 합니다.