동작 원리

대부분의 탐욕 알고리즘은 같은 뼈대를 가집니다. 후보를 어떤 기준으로 정렬하거나 우선순위 큐에 넣고, 하나씩 꺼내면서 지금까지의 선택과 충돌하지 않으면 받아들입니다. 이 장에서는 작은 예제로 구간 스케줄링, 허프만 부호화, 회의실 배정이 실제로 어떻게 움직이는지 따라가 봅니다.

구간 스케줄링(활동 선택)

회의실 하나에 신청이 여러 개 들어왔고, 서로 겹치지 않게 가장 많은 회의를 넣고 싶습니다. 각 회의는 반열린 구간 [시작, 끝)이라서 한 회의가 4시에 끝나면 다음 회의는 4시에 시작할 수 있습니다. 탐욕 기준은 "끝나는 시간이 가장 이른 회의부터"입니다.

def trace(intervals):
    last_end = float("-inf")
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        ok = start >= last_end
        print(f"({start}, {end}) last_end={last_end} -> {'선택' if ok else '건너뜀'}")
        if ok:
            last_end = end


trace([(1, 3), (2, 5), (4, 7), (1, 8), (6, 9), (8, 10)])

끝나는 시간순으로 정렬한 뒤의 진행은 다음과 같습니다.

결과는 (1, 3), (4, 7), (8, 10)의 3개이며, 이보다 많이 고를 수 없습니다.

다른 기준은 왜 틀릴까

그럴듯해 보이는 기준도 반례 하나로 무너집니다.

가장 일찍 끝나는 회의를 고르면 남은 시간이 가장 많이 남습니다. 탐욕 해의 k번째 회의는 어떤 해의 k번째 회의보다 늦게 끝나지 않는다는 것을 귀납법으로 보일 수 있는데, 이것이 앞서 나가기 논법입니다.

허프만 부호화

허프만 부호화는 자주 나오는 기호에 짧은 비트열을, 드문 기호에 긴 비트열을 주어 전체 길이를 최소로 만드는 접두 부호를 만듭니다. 탐욕 기준은 "가장 가벼운 두 덩어리를 합친다"입니다. 빈도가 a=5, b=9, c=12, d=13, e=16, f=45인 예를 따라가 봅니다.

import heapq

freq = {"a": 5, "b": 9, "c": 12, "d": 13, "e": 16, "f": 45}
heap = [(w, ch) for ch, w in freq.items()]
heapq.heapify(heap)
total = 0
while len(heap) > 1:
    w1, x = heapq.heappop(heap)
    w2, y = heapq.heappop(heap)
    total += w1 + w2
    print(f"{x}({w1}) + {y}({w2}) = {w1 + w2}")
    heapq.heappush(heap, (w1 + w2, x + y))
print("전체 비트 수:", total)  # 224

완성된 트리에서 f는 깊이 1, c·d·e는 깊이 3, a·b는 깊이 4입니다. 각 기호의 부호 길이는 그 깊이와 같고, 빈도와 길이를 곱해 더하면 45 + 36 + 39 + 48 + 20 + 36 = 224비트입니다. 합칠 때마다 생긴 무게의 합(14 + 25 + 30 + 55 + 100)과 같다는 점도 확인할 수 있습니다. 고정 길이 3비트를 쓰면 300비트이므로 약 25%를 줄인 셈입니다.

가장 가벼운 두 기호가 가장 깊은 곳에 형제로 놓이는 최적 트리가 항상 존재한다는 것이 교환 논법으로 증명됩니다. 더 무거운 기호가 더 깊은 곳에 있다면 두 기호를 맞바꿔도 비용이 늘지 않기 때문입니다.

회의실 배정(최소 플랫폼)

이번에는 모든 회의를 다 열어야 하고, 필요한 회의실 수의 최솟값을 구합니다. 기차역에서 필요한 플랫폼 수를 구하는 문제도 같은 구조입니다. 회의를 시작 시간순으로 보면서, 사용 중인 방들의 끝 시간을 최소 힙에 넣어 둡니다. 가장 먼저 비는 방이 지금 회의 시작 전에 비면 그 방을 다시 쓰고, 아니면 방을 하나 더 엽니다.

import heapq


def min_rooms(meetings):
    ends = []  # 사용 중인 방들의 끝 시간(최소 힙)
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)  # 가장 먼저 빈 방을 다시 쓴다
        else:
            heapq.heappush(ends, end)     # 새 방을 연다
    return len(ends)


print(min_rooms([(9, 10), (9, 12), (10, 11), (11, 13), (12, 13)]))  # 2

기차 플랫폼처럼 도착과 출발이 같은 시각이면 플랫폼을 함께 쓸 수 없는 규칙이라면 ends[0] <= start를 ends[0] < start로 바꿉니다. 구간 끝을 포함하는지 여부는 탐욕 알고리즘에서 가장 흔한 실수의 원인입니다.

정리

• 탐욕 알고리즘의 뼈대는 "기준대로 정렬하거나 힙에 넣고, 하나씩 꺼내 충돌하지 않으면 받아들이기"입니다.
• 구간 스케줄링은 가장 일찍 끝나는 구간, 허프만 부호화는 가장 가벼운 두 덩어리, 회의실 배정은 가장 먼저 비는 방이 기준입니다.
• 그럴듯한 다른 기준은 작은 반례로 쉽게 깨지므로 기준을 고른 이유를 반드시 설명할 수 있어야 합니다.
• 구간 끝 포함 여부(<와 <=)를 문제 조건에 맞게 정해야 합니다.