그리디

🎯 학습 목표

이 강을 마치면 그리디(탐욕법)가 언제 성립하는지 두 가지 조건으로 판단할 수 있습니다. 그리고 회의실 배정·거스름돈·최소 동전 같은 대표 문제를 풀고, 그리디가 틀리는 반례를 직접 만들 수 있게 됩니다.

그리디는 코드가 짧고 빠르지만 가장 위험한 접근이기도 합니다. 많은 초보자가 "그럴듯해 보여서" 그리디로 풀었다가 일부 테스트에서만 틀립니다. 이 강의 절반은 "언제 쓰면 안 되는가"에 씁니다.

💡 매 순간 최선을 고른다

그리디는 지금 시점에서 가장 좋아 보이는 선택을 하고 되돌아보지 않는 방법입니다. 15·16강처럼 모든 경우를 보지 않으므로 훨씬 빠릅니다.

회의실 배정 — 그리디가 통하는 예

  회의 목록 (시작, 종료)
   A(1,4)  B(3,5)  C(0,6)  D(5,7)  E(8,9)  F(5,9)

  전략: '끝나는 시간이 빠른 것'부터 고른다

   정렬 후: A(1,4) B(3,5) C(0,6) D(5,7) E(8,9) F(5,9)
                                  ↑ 종료 시각 기준

   A(1,4) 선택 → 현재 시각 4
   B(3,5) 시작 3 < 4 → 겹침, 버림
   C(0,6) 시작 0 < 4 → 겹침, 버림
   D(5,7) 시작 5 ≥ 4 → 선택, 현재 시각 7
   E(8,9) 시작 8 ≥ 7 → 선택, 현재 시각 9
   F(5,9) 시작 5 < 9 → 겹침, 버림

   답: A, D, E → 3개

  ▲ 왜 '종료 시간'인가
    빨리 끝날수록 뒤에 남는 시간이 많다.
    → 남은 선택지를 최대로 보존하는 선택이다

  ▲ 왜 '시작 시간'이면 안 되는가
    C(0,6) 을 먼저 고르면 6까지 아무것도 못 한다.
    가장 일찍 시작하지만 가장 손해다.

  ▲ 왜 '짧은 회의'면 안 되는가
    반례: (1,5) (4,6) (5,9)
    짧은 (4,6) 을 고르면 나머지 둘 다 못 쓴다 → 1개
    종료 기준이면 (1,5), (5,9) → 2개

여기서 보이듯 그리디의 핵심은 "무엇을 기준으로 고를 것인가"입니다. 같은 문제여도 기준이 틀리면 답이 틀립니다.

📖 성립 조건 두 가지

그리디가 항상 최적해를 주려면 두 조건을 만족해야 합니다.

조건	내용	확인 방법
탐욕 선택 속성	지금의 최선이 전체 최적해에 포함된다	"이 선택을 포함하는 최적해가 반드시 있는가"
최적 부분 구조	남은 문제의 최적해가 전체 최적해를 만든다	"하나 고른 뒤 남은 문제가 같은 모양인가"

그리디가 틀리는 대표 반례 — 최소 동전

  동전 [1, 3, 4] 로 6원을 만들 때 최소 개수는?

  [그리디]  큰 것부터
   4 → 남은 2
   1 → 남은 1
   1 → 남은 0
   총 3개

  [실제 최적]
   3 + 3 = 6
   총 2개  ★

  ▲ 그리디가 틀렸다
    4를 고른 순간 최적해에서 멀어졌는데
    되돌아보지 않기 때문이다

  ▲ 그런데 한국 화폐 [1, 5, 10, 50, 100, 500] 에서는
    그리디가 항상 옳다.
    큰 단위가 작은 단위의 배수 구조로 짜여 있기 때문이다.

  ▲ 교훈
    "동전 문제는 그리디"가 아니라
    "이 동전 구성에서 그리디가 성립하는가"를 봐야 한다.
    성립하지 않으면 동적 계획법으로 간다 (26강).

  실무에서 그리디를 검증하는 방법

   ① 반례를 5분간 찾아본다
      특히 작은 입력, 경계값, 극단적으로 치우친 값
   ② 완전 탐색 결과와 비교한다  ← 가장 확실 ★
      작은 입력으로 브루트포스와 그리디 답을 대조
   ③ 증명해 본다 (교환 논법)
      "최적해에 그리디 선택이 없다고 가정해도
       바꿔 넣으면 여전히 최적이다"를 보인다

실전에서는 ②번이 가장 실용적입니다. 15강의 완전 탐색 코드를 작은 입력으로 돌려 그리디 결과와 비교하면, 몇 분 만에 그리디의 타당성을 확인할 수 있습니다.

💻 실전 예제 — 통하는 경우와 안 통하는 경우

from itertools import combinations


def max_meetings(meetings):
    """겹치지 않게 최대한 많은 회의 배정 → 그리디가 옳다"""
    meetings.sort(key=lambda m: m[1])   # 종료 시각 기준 정렬  ★
    count = 0
    current_end = 0
    for start, end in meetings:
        if start >= current_end:        # 겹치지 않으면
            count += 1
            current_end = end
    return count


def min_coins_greedy(coins, amount):
    """큰 동전부터 쓰는 그리디 → 항상 옳지는 않다"""
    coins = sorted(coins, reverse=True)
    count = 0
    for c in coins:
        take = amount // c
        count += take
        amount -= c * take
    return count if amount == 0 else -1


def min_coins_dp(coins, amount):
    """동적 계획법 → 항상 옳다 (26강 예고)"""
    INF = float("inf")
    dp = [0] + [INF] * amount           # dp[i] = i원을 만드는 최소 개수
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
    return dp[amount] if dp[amount] != INF else -1


rooms = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print(max_meetings(rooms))                    # 3

print(min_coins_greedy([1, 5, 10, 50], 78))   # 8  (50+10+10+5+1+1+1)
print(min_coins_dp([1, 5, 10, 50], 78))       # 8  같다

print(min_coins_greedy([1, 3, 4], 6))         # 3  ← 틀린 답
print(min_coins_dp([1, 3, 4], 6))             # 2  ← 정답

코드를 줄 단위로 보겠습니다.

• meetings.sort(key=lambda m: m[1]) — 튜플의 두 번째 값(종료 시각)으로 정렬합니다. 이 한 줄이 알고리즘의 전부입니다. 기준을 m[0]으로 바꾸면 답이 틀립니다.
• if start >= current_end — 이전 회의가 끝난 뒤 시작하면 선택합니다. 등호를 포함할지는 "끝나는 순간 바로 시작해도 되는가"라는 문제 조건에 달렸습니다.
• take = amount // c — 그 동전을 최대한 많이 씁니다. 이것이 "지금의 최선"입니다.
• dp = [0] + [INF] * amount — DP 배열입니다. dp[0] = 0(0원은 동전 0개), 나머지는 아직 못 만듦을 뜻하는 무한대로 둡니다.
• if c <= i and dp[i - c] + 1 < dp[i] — "i원을 만들려면, i-c원을 만든 뒤 동전 c를 하나 더"라는 관계입니다. 모든 동전을 다 시도해 보고 최소를 고르므로 그리디처럼 놓치지 않습니다.
• DP의 복잡도는 O(amount × 동전 수)입니다. 그리디의 O(동전 수)보다 느리지만 항상 정답입니다.

마지막 두 줄이 이 강의 핵심입니다. 같은 문제, 같은 함수, 다른 동전 구성에서 그리디가 3, DP가 2를 냅니다. 동전이 [1, 5, 10, 50]일 때는 둘이 같았습니다. 입력에 따라 그리디의 정당성이 달라진다는 것을 보여 줍니다.

⚠️ 자주 하는 실수

첫째, 검증 없이 그리디를 씁니다. 가장 흔하고 가장 아픈 실수입니다. 제출 전에 반례를 찾아보거나 완전 탐색과 대조하세요. 통과 못 한 뒤에 원인을 찾는 것보다 훨씬 빠릅니다.

둘째, 정렬 기준을 잘못 잡습니다. 그리디 문제의 대부분은 "무엇을 기준으로 정렬하는가"가 답입니다. 후보가 여럿이면 작은 예제로 각각 확인해 보세요.

셋째, 되돌아가야 하는 문제에 씁니다. "앞선 선택을 취소해야 더 나은 답이 나오는" 구조면 그리디가 아니라 DP나 백트래킹입니다.

넷째, "빨라 보여서" 고릅니다. 그리디는 O(n log n) 정도로 빠르지만, 틀린 답을 빨리 내는 것은 의미가 없습니다. 입력 범위가 작으면 완전 탐색이 더 안전한 선택일 때가 많습니다.

다섯째, 부분 점수를 노려 그리디를 냅니다. 전략적으로는 가능하지만, 어느 부분이 틀릴지 모른다는 점을 인지하고 내야 합니다. 시간이 남으면 반드시 검증하세요.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	그리디 = 지금의 최선, 되돌아보지 않음
2	성립 조건: 탐욕 선택 속성 + 최적 부분 구조
3	회의실 배정은 종료 시각 기준
4	동전 구성에 따라 그리디가 틀린다
5	검증은 완전 탐색과 대조가 가장 확실
6	정렬 기준이 곧 알고리즘
7	되돌아가야 하면 DP·백트래킹

지금 해 볼 것은 동전 [1, 3, 4]에서 그리디와 DP가 갈리는 다른 금액을 찾아보는 것입니다. 6원 외에도 여러 개가 있습니다. 반례를 직접 찾아보면 그리디를 의심하는 습관이 생깁니다.

다음 18강 「연결 리스트」부터는 다시 자료구조로 돌아갑니다. 3강의 배열과 정반대 성질 — 중간 삽입·삭제는 O(1)인데 인덱스 접근은 O(n) — 을 가진 구조이고, 19강 트리와 22강 그래프의 토대가 됩니다.

📚 참고 자료

• Sorting Techniques — Python 공식 문서
• float() — Python 공식 문서
• itertools.combinations — Python 공식 문서