탐욕 알고리즘의 개념

탐욕 알고리즘(greedy algorithm)은 문제를 여러 단계의 선택으로 나누고, 각 단계에서 지금 가장 좋아 보이는 것을 고른 뒤 그 선택을 다시 돌아보지 않는 설계 방법입니다. 모든 경우를 따져 보는 완전 탐색이나 부분 문제의 답을 표에 모아 두는 동적 계획법과 달리, 탐욕 알고리즘은 한 길만 따라갑니다. 그래서 코드가 짧고 빠르지만, 그 한 길이 정말 최적의 답으로 이어진다는 것을 따로 증명해야 합니다.

핵심 용어

탐욕 알고리즘이 옳으려면 탐욕 선택 속성과 최적 부분 구조가 함께 성립해야 합니다. 앞의 것은 "첫 선택이 틀리지 않는다"는 보장이고, 뒤의 것은 "첫 선택 뒤에 남은 문제도 같은 방식으로 풀면 된다"는 보장입니다. 두 성질이 있으면 귀납적으로 모든 선택이 옳다는 결론이 나옵니다.

교환 논법의 흐름

탐욕 알고리즘을 증명할 때 가장 많이 쓰는 방법이 교환 논법입니다. 흐름은 늘 비슷합니다.

1. 임의의 최적해 OPT를 하나 잡습니다.
2. OPT가 탐욕 해와 처음으로 달라지는 지점을 찾습니다.
3. 그 지점의 OPT 원소를 탐욕이 고른 원소로 바꿔도 해가 여전히 올바르고 값이 나빠지지 않음을 보입니다.
4. 이 교환을 반복하면 OPT를 탐욕 해로 바꿀 수 있으므로 탐욕 해도 최적입니다.

예를 들어 겹치지 않는 회의를 가장 많이 고르는 문제에서는 "가장 일찍 끝나는 회의"를 먼저 고릅니다. 어떤 최적해의 첫 회의를 가장 일찍 끝나는 회의로 바꿔도, 새 회의는 원래 회의보다 늦게 끝나지 않으므로 뒤의 회의들과 겹치지 않습니다. 회의 개수는 그대로이니 이 교환은 손해가 없습니다.

탐욕이 통하는 경우: 거스름돈

동전으로 거스름돈을 줄 때 큰 동전부터 최대한 쓰는 방법은 가장 익숙한 탐욕 알고리즘입니다. 한국 동전(10, 50, 100, 500원)처럼 잘 설계된 동전 체계에서는 이 방법이 항상 동전 수를 최소로 만듭니다.

def greedy_coins(coins, amount):
    """큰 동전부터 최대한 쓴다. 정확히 맞출 수 없으면 None."""
    count = 0
    for coin in sorted(coins, reverse=True):
        take, amount = divmod(amount, coin)
        count += take
    return count if amount == 0 else None


print(greedy_coins([10, 50, 100, 500], 780))  # 7 (500 + 100 * 2 + 50 + 10 * 3)

탐욕이 실패하는 경우: 반례

동전이 1, 3, 4원이고 6원을 거슬러 줘야 한다고 해 봅시다. 탐욕은 4원을 먼저 쓰고 1원 두 개를 더해 동전 3개를 씁니다. 그러나 3원 두 개면 동전 2개로 충분합니다. 첫 선택(4원)이 최적해에 들어가지 않으므로 탐욕 선택 속성이 깨진 것입니다. 이런 경우에는 동적 계획법으로 모든 금액의 최소 동전 수를 계산해야 합니다.

def min_coins(coins, amount):
    """동적 계획법: best[a] = a원을 만드는 최소 동전 수."""
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else None


print(greedy_coins([1, 3, 4], 6), min_coins([1, 3, 4], 6))  # 3 2

증명이 어려울 때: 작은 입력으로 비교하기

증명을 세우기 전에, 또는 증명이 맞는지 의심될 때는 작은 입력에서 탐욕 해와 정답(완전 탐색이나 동적 계획법)을 비교해 보는 것이 가장 빠른 확인 방법입니다. 반례가 하나라도 나오면 그 탐욕 기준은 틀린 것입니다.

def find_counterexample(coins, limit=100):
    for amount in range(1, limit + 1):
        g, d = greedy_coins(coins, amount), min_coins(coins, amount)
        if g != d:
            return amount, g, d
    return None


print(find_counterexample([1, 3, 4]))           # (6, 3, 2)
print(find_counterexample([10, 50, 100, 500]))  # None

반례가 나오지 않았다고 해서 증명이 된 것은 아니지만, 틀린 기준을 일찍 버리는 데는 매우 효과적입니다.

언제 탐욕을 떠올릴까

• 정렬하거나 우선순위 큐에서 꺼내는 순서대로 처리하면 될 것 같은 문제
• "최대 개수", "최소 비용", "최소 개수"를 묻고 선택이 서로 크게 얽히지 않는 문제
• 구간, 마감 시간, 가중치처럼 하나의 기준으로 줄 세울 수 있는 데이터가 있는 문제
• 동적 계획법의 상태가 너무 커서 더 단순한 규칙이 필요한 문제

정리

• 탐욕 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하고 되돌리지 않습니다.
• 옳으려면 탐욕 선택 속성과 최적 부분 구조가 필요하며, 보통 교환 논법으로 증명합니다.
• 동전 1, 3, 4원과 6원처럼 반례가 하나라도 있으면 그 기준은 틀린 것이며, 이때는 동적 계획법을 씁니다.
• 증명 전에 작은 입력에서 완전 탐색과 비교하면 틀린 기준을 빨리 걸러 낼 수 있습니다.