10. 탐욕법 (그리디)

매 순간 "지금 당장 가장 좋아 보이는 선택"을 하는 전략입니다. 편의점에서 거스름돈을 줄 때 큰 동전부터 척척 골라 주는 것처럼요. 단순해서 매력적이지만, 함정도 여기 있습니다. "지금 최선"이 "전체 최선"으로 이어진다는 보장이 없거든요. 그래서 그리디는 "이 선택이 정말 최적으로 이어지는가"를 의심하고 확인하는 감각이 핵심입니다. 그리고 그 확인은 대부분 정렬(3장)에서 시작합니다.

이 한 챕터에서 배우는 것:

• 그리디가 통하는 조건 (탐욕 선택 속성 · 최적 부분 구조)
• 정렬 후 하나씩 선택하는 그리디의 대표 패턴
• 대표 예제 두 개: 거스름돈, 회의실 배정
• 반례를 떠올려 그리디를 의심하는 사고법

그리디가 뭐죠?

문제를 여러 단계로 쪼갠 뒤, 각 단계에서 되돌아보지 않고 그 순간 최선만 고르는 방법입니다.

동전으로 800원을 거슬러 준다고 해봅시다. 500원 하나, 그다음 100원 세 개. 끝. 이미 낸 동전을 "역시 무를게요" 하고 되돌리지 않죠. 매번 낼 수 있는 가장 큰 동전만 고르면 답이 나옵니다. 이게 그리디예요.

DP(11장)가 "모든 경우를 따져 최적을 찾는다"면, 그리디는 "따지지 않고 그냥 지금 최선을 믿고 간다" 입니다. 그래서 훨씬 빠르지만, 그 믿음이 틀리면 오답입니다.

그리디가 통하는 조건

아무 문제에나 그리디를 들이대면 안 됩니다. 두 가지가 성립할 때만 정답이 보장돼요.

1. 탐욕 선택 속성: 매 순간의 지역적 최선을 골라도, 그게 전체 최적의 일부가 된다.
2. 최적 부분 구조: 큰 문제의 최적해가, 작은 문제의 최적해로 쪼개진다.

💡 실전에서 이걸 수학적으로 증명하긴 어렵습니다. 대신 "내 그리디 규칙을 깨뜨리는 반례가 있나?" 를 몇 초간 상상해 보세요. 반례가 안 떠오르면 그리디, 금방 떠오르면 DP나 완전탐색으로 방향을 트는 겁니다.

예제 1: 거스름돈

동전 종류 [500, 100, 50, 10]으로 n원을 거슬러 줄 때, 동전 개수를 최소로 하려면?

직관은 뻔합니다. 큰 동전부터 최대한 많이 쓴다. 정렬해서 큰 것부터 훑으면 되죠.

def change(n, coins):
    coins.sort(reverse=True)   # 큰 동전부터
    count = 0
    for coin in coins:
        count += n // coin     # 이 동전을 몇 개 쓸 수 있나
        n %= coin              # 쓰고 남은 금액
    return count

print(change(1260, [500, 100, 50, 10]))   # 6  (500x2 + 100x2 + 50x1 + 10x1)
print(change(800, [500, 100, 50, 10]))    # 4  (500x1 + 100x3)

동전 종류가 k개면 반복은 k번뿐입니다. O(k) (정렬 포함이면 O(k log k)). 금액 n이 아무리 커도 나눗셈 한 번으로 처리하니 순식간이에요.

💡 이 그리디가 통하는 건 동전이 배수 관계(100은 50의 2배, 50은 10의 5배...)이기 때문입니다. 이 조건이 깨지면 바로 무너져요. 아래에서 확인합니다.

반례로 그리디를 의심하기

거스름돈 그리디를 그냥 믿어도 될까요? 동전을 [4, 3, 1]로 바꿔 6원을 만들어 봅시다.

• 그리디: 4 먼저 → 남은 2 → 4는 안 됨 → 1 두 개 → 총 3개 (4+1+1)
• 실제 최적: 3+3 → 2개

그리디가 틀렸습니다. 4를 욕심내는 바람에 더 나은 3+3을 놓친 거예요. 이럴 땐 그리디를 버리고 DP로 풀어야 합니다.

def change_dp(n, coins):
    INF = float('inf')
    dp = [0] + [INF] * n           # dp[i] = i원을 만드는 최소 동전 수
    for i in range(1, n + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[n]

print(change_dp(6, [4, 3, 1]))   # 2   (3+3, 그리디의 3개보다 적다)

💡 "큰 것부터 고르면 되겠지" 라는 직관이 들 때, 반드시 작은 반례를 손으로 만들어 보세요. [4,3,1]처럼 배수가 아닌 경우, 뒤가 막히는 경우를 노리면 반례가 잘 나옵니다. 반례 하나면 그리디는 탈락입니다.

정렬 후 선택 패턴

그리디의 8할은 "어떤 기준으로 정렬하느냐" 로 판가름 납니다. 정렬 기준만 제대로 잡으면, 그 뒤는 앞에서부터 하나씩 훑으며 조건에 맞는 것만 취하면 끝이거든요. 3장의 key 정렬이 여기서 진가를 발휘합니다.

패턴은 늘 이렇습니다.

1. 정렬 기준을 정한다 (이게 그리디의 정체).
2. 정렬한다.
3. 앞에서부터 훑으며 조건에 맞으면 취하고, 아니면 버린다.

예제 2: 회의실 배정

회의 여러 개의 (시작, 끝) 시간이 주어질 때, 겹치지 않게 최대 몇 개를 할 수 있을까요? (한 회의실입니다.)

핵심 질문: 뭘 기준으로 정렬할까요? 끝나는 시간이 빠른 회의부터 고르는 게 정답입니다. 빨리 끝날수록 남은 시간이 많아져 뒤에 더 많은 회의를 넣을 수 있으니까요.

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

data = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
print(max_meetings(data))   # 3   ((1,4) -> (5,7) -> (8,11) 겹침없이 최대 3개)

정렬이 O(n log n), 이후 한 번 훑는 게 O(n). 전체 O(n log n) 입니다.

💡 만약 시작 시간으로 정렬했다면? (0,6)을 제일 먼저 골라 6시까지 회의실을 통째로 묶어버려 손해입니다. 회의 개수로 정렬해도(길이 짧은 것부터) 반례가 나와요. "끝나는 시간"이 정답인 이유를 반례로 검증하는 이 과정이 곧 그리디 실력입니다.

여기서도 앞의 사고법이 그대로예요. 정렬 기준 후보(시작 / 끝 / 길이)를 두고 각각의 반례를 떠올려 살아남는 기준을 고른 겁니다.

정리

💡 그리디와 정렬은 한 몸입니다. "정렬 기준을 뭘로 잡지?" 라는 질문이 곧 "내 그리디 규칙이 뭐지?" 라는 질문이에요. 그래서 3장 정렬의 key 다루기가 이 챕터의 진짜 밑밥이었습니다.

직접 풀어보기

1. [10, 50, 100, 500] 동전으로 4720원을 거슬러 줄 때 최소 동전 수를 구해보세요. (정답: 13개)
2. 회의실 예제에서 정렬 기준을 key=lambda m: m[0] (시작 시간)으로 바꾸면 답이 몇으로 나오는지 확인하고, 왜 손해인지 설명해 보세요. (힌트: (0,6)이 발목을 잡습니다)
3. 1부터 시작해 어떤 수 k가 있을 때, k+1 이하의 모든 자연수를 만들 수 있게 하려면 다음에 어떤 수를 더해야 이득일까요? 동전(=수) 목록을 정렬해 앞에서부터 훑는 그리디로 "만들 수 없는 가장 작은 금액"을 찾아보세요. (힌트: 지금까지 target-1까지 만들 수 있는데 다음 동전이 target보다 크면, target은 못 만듭니다) ```