[C#, Algorithm] 그라디(탐욕, 욕심쟁이) 알고리즘

■ 그라디(Greedy) 알고리즘

[그라디 알고리즘]

그라디(탐욕, 욕심쟁이) 알고리즘은 매 단계에서 “가장 좋아 보이는 선택”을 하는 알고리즘이다. 이 선택이 전체적으로도 최적일 거라는 가정 하에 작동한다.

• 항상 최적의 값을 계산하는것을 보장하진 않는다. 다만 최적에 “근사한 값”을 목표로 한다.

예시로 위 상황에서 항상 최적의 값(가장 짧은 KM)을 구하면 서울(40)→이천(80)→대구(30)의 순으로 총 150KM가 나온다. 하지만 서울→이천→대전→부산으로 가는 경로는 총 145KM이기 때문에 최적에 근사한 값을 내는 것을 확인할 수 있다.

 

예시) “손님에게 거스름돈을 줄 때 가장 적은 개수의 동전으로 거스름돈을 주려고 한다.”

사용 가능한 동전의 종류는 [500원,100원,50원,10원]일 때, 거슬러 줘야 할 동전의 최소 개수를 구하는 프로그램을 작성해 보자.

internal class Greedy
{
    public Dictionary<int, int> CalculateChange(int[] coin, int change)
    {
        // 1. 문제를 정렬 가능한 구조로 파악하기
        // - 여기서는 거슬러 줄 동전을 내림차순으로 정렬
        Array.Sort(coin, (a, b) => b.CompareTo(a));
        
        var result = new Dictionary<int, int>();

        // 2. 탐욕적인 기준 정의
        // - 여기서는 가장 큰 동전부터 선택
        for(var i = 0; i < coin.Length; i++) 
        {
            var cnt = change / coin[i];
            change %= coin[i];

            result.Add(coin[i], cnt);
        }

        // 3. 그 선택이 전체 최적을 보장하는지 검증
        // - 여기서는 남은 금액이 0원이면 최적해를 구함.
        if(change <= 0)
        {
            return result;
        }

        // 4. 최적해를 구하지 못하면 실패(-1, 남은 돈)를 반환
        result.Add(-1, change);
        return result;
    }
}

 

그라디 알고리즘을 적용할 때 따라야 할 표준적인 절차가 있다.

1. 문제를 정렬 가능한 구조로 파악한다.
   • 문제를 작은 부분 문제들로 나눌 수 있는지 확인하고, 각 부분 문제의 최적해를 조합했을 때 전체 문제의 최적해가 되는지 살펴본다.
   • 예를 들어, 거스름돈 문제에서는 동전 단위를 내림차순 정렬하여 큰 단위의 동전을 먼저 고려할 수 있다.
2. 탐욕적인 기준(Greedy 기준)을 정의한다.
   • 매 순간 어떤 선택이 가장 "좋은 선택"인지 판단할 기준을 세운다.
   • 예: 비용이 작거나, 가치가 크거나, 가장 빠르게 끝나는 것 등.
3. 그 선택이 전체 죄적을 보장하는지 검증한다.
   • 그라디 알고리즘이 항상 최적해를 보장하는지 수학적, 혹은 논리적으로 확인해야 한다.
   • 최적 부분구조와 탐욕 선택 속성을 모두 만족해야 한다.

Greedy Choice Property(최적 부분 구조)	문제를 부분 문제로 나눴을 때, 그 부문 문제의 최적해를 합치면 전체 문제의 최적해가 된다는 성질.
Optimal Substructure(탐욕 선택 속성)	전체 문제의 최적해가, 부분 문제의 최적해로부터 구성될 수 있는가?

 

위 문제에선 “가장 큰 동전을 먼저 선택한다”라는 조건으로 각 순간마다 가장 많은 금액을 줄 수 있도록(최선) 되어있다.

또한 620원을 500 + 120원으로 나눴다면, 120원에 대해서도 같은 방법(100→10)으로 거슬러 줄 수 있기 때문에 탐욕 선택 속성도 만족한다.

• 이 두 조건을 만족하므로, 그라디가 항상 죄적해를 보장한다.

 

▶ 반례

그런데 위 경우 항상 보장되는 것은 아니다. 동전 단위가 애매하면 반례가 생긴다. 동전 단위가 [500,400,100]이라면,

• 800원을 거슬러 줄 때 :
  • 그라디 : 500 + 100 + 100 + 100 = 동전 4개
  • 최적해 : 400 + 400 = 동전 2개 ← 최적!

반례가 존재한다는 건, 그라디 알고리즘을 쓰면 항상 최적해를 구할 수 없기 때문에 적용하면 안 된다.