[Week 04] Greedy algorithm

1. 정의

그리디(Greedy)는 매 단계에서 국소적으로 최선이라 판단되는 선택을 하고, 그 선택을 취소하지 않은 채 끝까지 밀어붙여 전체 해를 구성하는 방법이다. 장점은 압도적인 단순함과 속도, 단점은 항상 정답을 보장하지 않는다는 점.

2. 성립 조건

• 선택 속성(Greedy choice property): 매 단계의 최선 선택이 전체 최적해의 일부로 확장 가능해야 한다.
• 최적 부분 구조(Optimal substructure): 전체 최적해가 부분 문제의 최적해들로 구성되어야 한다.

이 두 조건이 성립하면 그리디가 정답을 보장한다. 성립하지 않으면 빠르지만 오답이 될 수 있다.

3. 전형적 패턴

• 정렬 + 선형 스캔: 기준을 정의하고 정렬한 뒤, 앞/뒤에서 하나씩 선택.
• 우선순위 큐(힙): 매 순간 가장 좋은 후보를 즉시 꺼내기.
• 몫/나머지 반복: 거스름돈처럼, 남은 값으로 몫/나머지를 갱신.
• 인터벌 선택: 끝나는 시간, 시작 시간 등 핵심 기준 하나를 고정하고 탐욕 선택.

4. 잘 통하는 대표 문제

① 동전 거스름(11047 유형)

coins = [500, 100, 50, 10]
amount = 4720
cnt = 0
for c in coins:
    cnt += amount // c
    amount %= c
print(cnt)

핵심: 현재 남은 금액으로 몫/나머지를 갱신한다. M을 고정해 두고 계속 쓰면 오답.

② 활동 선택(회의실 배정)

끝나는 시간이 가장 빠른 활동부터 채택하면, 전체 선택 가능한 활동 수가 최대가 된다. (끝시간 오름차순 정렬 → 겹치지 않으면 채택)

③ 최소 신장 트리(MST)

• Kruskal: 간선을 가중치 오름차순으로 정렬, 사이클이 생기지 않으면 채택(Union-Find).
• Prim: 트리에 인접한 간선 중 가장 가벼운 간선을 확장(우선순위 큐).

④ 허프만 코딩

가장 빈도가 낮은 두 노드를 반복적으로 합치는 탐욕 선택으로 최적의 접두부 코드가 만들어진다.

5. 그리디가 깨지는 반례

동전 = [500, 400, 100], 금액 = 800
그리디: 500 + 100 + 100 + 100 = 4개
최적해: 400 + 400 = 2개  ← 그리디 실패

동전 = [1, 3, 4], 금액 = 6
그리디: 4 + 1 + 1 = 3개
최적해: 3 + 3 = 2개

따라서, 그리디를 쓰기 전에는 “왜 이 기준이 항상 맞는가?”를 반드시 점검해야 한다.

6. 증명 스케치: 왜 맞는가

• 교환 논법(Exchange argument): 임의의 최적해가 있다고 가정하고, 가장 앞의 선택을 그리디 선택으로 바꿔도 품질이 나빠지지 않음을 보인다. 이를 반복하면 그리디 해도 최적해임이 성립.
• 귀납/단조성: 한 단계의 최선 선택 후 남은 부분 문제에서도 같은 구조가 반복됨을 보인다.

7. 구현 팁 & 복잡도

• 정렬은 보통 O(N log N). 이후는 선형 스캔 O(N).
• 힙을 쓰면 매 선택 O(log N). (Prim, 허프만 등)
• 불변식을 명확히: “지금까지의 선택은 항상 유효하다”를 유지.
• 경계/예외: 동등 값, 빈 입력, 0/음수, 오버플로우 주의.

8. DP / 백트래킹과 비교

그리디

• 빠름, 구현 간단
• 정답 보장은 문제 성질에 의존

DP

• 전역 최적 보장
• 상태 정의/점화식 필요, 메모리 사용↑

백트래킹

• 정확하지만 느림
• 가지치기로 평균 성능 개선

9. 코드 스니펫

① 동전 거스름 (정규 화폐)

def greedy_change(coins, amount):
    cnt = 0
    for c in sorted(coins, reverse=True):
        if c <= 0:
            continue
        cnt += amount // c
        amount %= c
    return cnt

② 활동 선택

def activity_selection(intervals):
    intervals.sort(key=lambda x: x[1])  # 끝시간 기준
    res = []
    last_end = -float('inf')
    for s,e in intervals:
        if s >= last_end:
            res.append((s,e))
            last_end = e
    return res

③ Kruskal (개요)

def kruskal(n, edges):
    parent = list(range(n))
    def find(x):
        while x != parent[x]:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a,b):
        ra, rb = find(a), find(b)
        if ra == rb: return False
        parent[rb] = ra
        return True

    mst = []
    for w,u,v in sorted(edges):
        if union(u,v):
            mst.append((w,u,v))
    return mst

10. 체크리스트

• 탐욕 기준이 항상 맞는지 증명(교환 논법/반례 탐색)했는가?
• 정렬/우선순위 기준이 문제의 목표와 정확히 일치하는가?
• “현재 남은 값”을 기준으로 갱신하고 있는가? (거스름: 몫/나머지)
• 동률 처리 규칙이 필요한가? (예: 종료시간 동일 시 시작시간 순)
• 반례 케이스(비정규 화폐 등)에 대한 대체 접근(DP)을 준비했는가?

그리디는 빠른 1차 시도로 훌륭하다. 다만 보장이 필요한 문제에서는 반드시 조건을 확인하거나, DP/증명으로 보강하자.