그리디인 줄 알았는데 DP였다

"다 맞았는데 왜 틀려요?" — 탐욕법 문제에서 이 말 한 번이라도 해봤으면 손.

코테 단골 유형인 greedy. 쉬운 것 같으면서 함정이 깊다. "이거 탐욕적 접근 아닌가?" 싶은 문제에서 점화식을 써야 하는 경우가 많고, 반대로 DP로 풀다가 시간 초과 나는 문제가 탐욕법으로 깔끔하게 풀리기도 한다. 오늘은 이 경계선을 정리해본다.

#탐욕법이 통하려면

두 조건 — 탐욕적 선택 속성(지금의 최선이 나중에도 최선)과 최적 부분 구조(큰 문제의 최적해가 작은 문제의 최적해를 포함). 동적 프로그래밍도 후자는 동일하지만, 선택을 번복할 수 있다는 게 차이다. 문제는 시험장에서 이걸 엄밀하게 증명할 시간이 없다는 점이고, 그래서 패턴 학습이 중요하다.

#거스름돈 — 가장 유명한 함정

동전이 [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

근데 동전이 [7, 5, 1]이고 금액이 10이면 이야기가 달라진다.

• 큰 것부터 넣기: 7 → 1 → 1 → 1 = 4개

• 정답: 5 + 5 = 2개

왜 실패하냐면, 7을 선택하는 순간 남은 3을 1로밖에 채울 수 없다. 더 작은 동전을 먼저 쓰는 게 오히려 전체 개수를 줄이는 경우가 생기는 거다. 동전 단위가 서로 배수 관계일 때만 "큰 것 우선" 전략이 보장된다. 한국 원화가 정확히 이 구조라 교과서 예제로 매번 등장하는데, 실전에서는 단위가 불규칙한 변형이 출제된다. 그때는 점화식 없이는 답을 보장할 수 없다.

이 문제의 DP 풀이는 dp[i] = min(dp[i - coin] + 1) 형태로 O(금액 × 동전 수)에 돌아간다. 단위가 몇 개 안 되면 충분히 빠르다. "최소 개수" 류 문제에서 단위 간 관계가 명확하지 않으면, 고민하지 말고 동적 프로그래밍부터 짜는 게 안전하다.

#활동 선택 — 정석적인 탐욕 문제

회의실 배정. 종료 시간 기준으로 정렬하면 된다.

def max_meetings(meetings):
    meetings.sort(key=lambda x: x[1])
    result, end = 0, 0
    for s, e in meetings:
        if s >= end:
            result += 1
            end = e
    return result

가장 빨리 끝나는 회의를 고르면 남은 시간이 최대한 확보된다. 이후 선택지가 줄어들지 않으니 반례가 없다. 정렬 한 번이면 판이 정리되는 구조 — 이런 패턴이 보이면 탐욕적 접근을 강하게 의심해도 좋다.

#2분 판별 체크리스트

#찝찝하면 점화식부터 짜라

내 기준은 단순하다. 2분 안에 반례가 안 떠오르고, 위 체크리스트에서 탐욕 쪽이면 그걸로 간다. 조금이라도 찝찝하면 동적 프로그래밍부터 작성한다.

DP가 TLE 나면 그때 탐욕적 풀이를 다시 고민해도 늦지 않다. 시간복잡도 초과는 최적화 문제지, 정합성 문제가 아니니까. 반면 탐욕법으로 제출했다가 70%에서 오답이 뜨면 — 그건 로직 한두 줄 고쳐서 해결되는 게 아니다. 풀이 방향 자체가 틀렸다는 신호다.

현장에서 제일 위험한 건 "이게 왜 맞는지 설명은 못 하겠는데 예제는 다 통과하네" 상태로 제출 버튼을 누르는 것. 예제 3~4개가 통과해도 반례 하나면 끝이다. 확신이 서지 않으면 점화식이 시간은 더 걸려도 훨씬 안전한 선택이다. 속도 최적화는 AC를 받은 뒤에 해도 된다.