탐욕법 — Greedy Algorithm

이 토픽을 마치면

탐욕법이 작동하는 원리를 이해하고, 언제 적용할 수 있는지 판단할 수 있으며, 대표 문제를 직접 풀 수 있습니다.

핵심 아이디어

편의점에서 1,260원을 거슬러 줘야 합니다. 동전은 500원, 100원, 50원, 10원이 있습니다.

직관적인 방법: 가장 큰 동전부터 최대한 쓴다.

def coin_change(amount):
    coins = [500, 100, 50, 10]
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count

print(coin_change(1260))  # 6개 (500×2 + 100×2 + 50×1 + 10×1)

매 단계에서 지금 당장 최선인 선택을 합니다. 과거를 돌아보지 않고, 미래를 내다보지 않습니다. 이것이 탐욕법(Greedy Algorithm)입니다.

왜 "탐욕"인가

탐욕법의 특징:

1. 지역 최적(local optimum): 현재 시점에서 가장 좋은 선택
2. 되돌림 없음: 한번 선택하면 번복하지 않음
3. 전역 최적(global optimum) 보장 조건: 특정 조건이 만족될 때만 전체 최적해가 됨

거스름돈 문제에서 500원짜리를 먼저 쓰는 것은 직관적으로 맞습니다. 하지만 모든 문제에서 이 전략이 통하지는 않습니다.

탐욕법이 통하는 조건

탐욕법으로 최적해가 보장되려면 두 가지 성질이 필요합니다:

탐욕 선택 속성 (Greedy Choice Property)

매 단계의 최선 선택이 전체 최적해에 포함됩니다.

거스름돈 예시: 500원 동전을 최대한 쓰는 게 항상 최적에 포함됩니다. 왜냐하면 500원 = 100원 × 5이므로, 500원을 안 쓰면 무조건 동전 수가 늘어납니다.

최적 부분 구조 (Optimal Substructure)

큰 문제의 최적해가 부분 문제의 최적해를 포함합니다.

1260원의 최적해 = 500원 2개 선택 + "260원의 최적해". 나머지 260원도 같은 전략으로 풀 수 있습니다.

탐욕법이 실패하는 경우

동전이 [400, 300, 100]원이고 600원을 거슬러 줘야 한다면:

# 탐욕법: 400 + 100 + 100 = 3개
# 최적해: 300 + 300 = 2개

400원을 먼저 선택하면 나머지 200원을 100원 2개로 채워야 합니다. 하지만 300원 2개가 더 적은 수입니다. 큰 동전부터 쓰는 전략이 실패합니다.

이 경우 500, 100, 50, 10처럼 큰 동전이 작은 동전의 정수 배수가 아니기 때문입니다. 배수 관계가 깨지면 탐욕법이 최적해를 보장하지 못합니다. 이런 문제는 동적 계획법(DP)이 필요합니다.

대표 문제 1: 활동 선택 (Activity Selection)

회의실이 하나 있고, 여러 회의 요청이 들어왔습니다. 겹치지 않게 가장 많은 회의를 배치하려면?

def max_meetings(meetings):
    # 끝나는 시간 기준으로 정렬
    meetings.sort(key=lambda m: m[1])

    count = 0
    last_end = 0
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
    return count

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
print(max_meetings(meetings))  # 4개

탐욕 전략: 끝나는 시간이 가장 빠른 회의부터 선택합니다.

왜 이것이 최적인가: 일찍 끝나는 회의를 선택할수록 남은 시간이 많아져서 더 많은 회의를 넣을 수 있습니다. 이 문제는 탐욕 선택 속성이 수학적으로 증명되어 있습니다.

대표 문제 2: 분할 가능 배낭 (Fractional Knapsack)

배낭 용량이 50kg이고, 물건을 쪼개서 넣을 수 있을 때 가치를 최대화:

def fractional_knapsack(capacity, items):
    # 무게당 가치 기준 내림차순 정렬
    items.sort(key=lambda x: x[1] / x[0], reverse=True)

    total_value = 0
    for weight, value in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break
    return total_value

items = [(10, 60), (20, 100), (30, 120)]  # (무게, 가치)
print(fractional_knapsack(50, items))  # 240.0

탐욕 전략: 무게 대비 가치(가성비)가 높은 것부터 넣습니다.

주의: 물건을 쪼갤 수 없는 0-1 배낭 문제에서는 탐욕법이 최적해를 보장하지 않습니다. 0-1 배낭은 DP로 풀어야 합니다.

탐욕법 vs 완전탐색 vs DP

탐욕법은 빠르지만 조건이 맞을 때만 정답입니다. 조건이 안 맞으면 DP나 완전탐색을 써야 합니다.

코딩 테스트에서의 판단법

1. "가장 ~한 것부터 선택하면 될 것 같다" → 탐욕 후보
2. 반례를 만들어본다 → 반례가 없으면 탐욕 적용
3. 정렬 기준이 명확하다 → 탐욕 가능성 높음
4. "남은 부분도 같은 방식으로 풀 수 있다" → 최적 부분 구조 충족

탐욕법이 의심되면 작은 입력으로 반례를 먼저 찾아보세요. 반례가 나오면 DP로 전환합니다. 실전에서 탐욕 문제는 정렬이 핵심인 경우가 대부분입니다.

핵심 한 줄: 탐욕법은 "매 순간 최선을 고르면 전체 최선이 된다"는 전략입니다. 동전 거스름돈처럼 조건이 맞으면 O(n)에 풀리지만, 조건을 만족하지 않으면 오답을 냅니다.