그리디 vs DP: 같은 문제, 두 평결

"그리디와 동적 계획법은 같은 왕좌를 노리는 라이벌이야. 배낭 문제가 그 드라마를 통째로 보여 주지. 아이템을 쪼갤 수 있느냐, 규칙 하나만 바꾸면 왕관이 그리디에서 DP로 넘어가."

갈림길의 질문

그리디도 DP도 부분 문제로 해법을 지어. 그래서 최적화 문제 앞에서는 갈림길을 자주 만나. 빠른 그리디 선택에 헌신해도 되나, 아니면 DP의 샅샅이 탐색에 값을 치러야 하나? 판가름하는 질문은 greedy-choice 속성이 성립하느냐야. 국소적으로 최선인 선택에 헌신해도 전역 최적 해법이 언제나 도달 가능한 채로 남아 있느냐는 것. 그렇다면 그리디의 승리야. 더 빠르고 단순하고 테이블도 없지. 그리디 선택이 최선의 답을 막아 버리는 반례가 있다면 모든 선택을 고려하고 캐시하는 DP가 필요해. 다만 그리디 반례 하나는 그 규칙이 틀렸음을 증명할 뿐, 곧바로 DP만이 답이라는 뜻은 아니야.

배낭: 규칙 하나가 모든 걸 뒤집는다

알고리즘을 통틀어 가장 깔끔한 시범이야. 무게 한계가 있는 배낭과, 무게와 가치가 달린 아이템들:

분수 배낭(아이템의 일부를 취할 수 있음): 그리디가 최적이야. 무게당 가치로 정렬해서 비율 높은 것부터 담고, 다음 아이템이 다 안 들어가면 들어가는 만큼만 잘라 담아. 증명 가능하게 최적이야. 쪼갤 수 있는 한 비율 순서를 이길 방법이 없거든.
0/1 배낭(아이템마다 전부 아니면 전무): 그리디는 실패하고 DP가 필요해. 쪼갤 수 없으니 비율 최고 아이템을 담는 게 더 나은 조합을 밀어낼 수 있어. 해법은 지난 트랙의 2D DP, dp[item][capacity]야.

같은 아이템, 같은 무게, 같은 목표야. 그런데 '쪼갤 수 있어?' 규칙 하나가 맞는 도구를 한 줄짜리 그리디 정렬과 완전한 DP 테이블 사이에서 결정해. 패러다임 고르기의 축소판이지. 문제 제약의 작은 변화가 어느 전략이 옳은지를 통째로 뒤집을 수 있다는 것.

greedy-choice 속성을 증명하면 그리디를 쓸 수 있어. 반례는 그 그리디를 반증할 뿐, 다음 도구까지 자동으로 정해 주진 않아. 분수 배낭은 비율 그리디가 맞고, 정수 용량의 0/1 배낭에는 O(n·capacity) 의사다항 DP가 대표적이야.

선택의 비용

분수 배낭은 정렬 때문에 O(n log n) 시간이야. 정렬 구현에 따라 추가 공간이 필요할 수 있으니 무조건 O(1) 공간이라고 하진 마. 정수 용량 C를 쓰는 0/1 배낭 DP는 O(nC) 시간인데, 입력의 비트 길이를 기준으로 보면 의사다항이야. C가 커지면 meet-in-the-middle이나 근사, 다른 최적화가 더 맞을 수 있어.

피파의 고백

난 '배낭엔 DP'를 무슨 공리처럼 외웠고, 그래서 분수 배낭에까지 DP 테이블을 들이댔어. 그리디 정렬 한 줄이면 풀리는 문제에 완전한 과잉이었지. 아빠가 내가 무시한 제약 하나를 가리켰어. "아이템 쪼갤 수 있어? 그럼 그리디야." '배낭'이라는 같은 단어가 규칙 하나에 따라 서로 다른 두 개의 정답을 갖고 있었던 거야. 그 뒤로 문제의 제약을 목표만큼 꼼꼼히 읽게 됐어. 패러다임을 결정하는 건 목표가 아니라 제약인 때가 많으니까.

Code

분수(그리디) vs 0/1(DP) 배낭·python

# 분수 배낭: 그리디가 최적 (일부를 취할 수 있음).
def fractional_knapsack(items, capacity):   # items: (value, weight)
    items.sort(key=lambda it: it[0] / it[1], reverse=True)  # 최고 비율 먼저
    total = 0.0
    for value, weight in items:
        if capacity >= weight:
            total += value; capacity -= weight      # 통째로 취함
        else:
            total += value * (capacity / weight)     # 맞는 부분만 취함
            break
    return total

print(fractional_knapsack([(60,10),(100,20),(120,30)], 50))   # 240.0

# 0/1 배낭: 그리디 실패 (전부-아니면-전무), 그래서 DP 필요.
def knapsack_01(items, capacity):           # 지난 트랙의 2D DP
    n = len(items)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    for i in range(1, n+1):
        value, weight = items[i-1]
        for c in range(capacity+1):
            dp[i][c] = dp[i-1][c]                        # 아이템 i 건너뛰기
            if weight <= c:                               # 또는 취하기 (맞으면)
                dp[i][c] = max(dp[i][c], dp[i-1][c-weight] + value)
    return dp[n][capacity]

print(knapsack_01([(60,10),(100,20),(120,30)], 50))   # 220 — 그리디 비율은 이걸 놓쳐
# 같은 아이템. '쪼갤 수 있어?' 가 결정: 그리디 (분수) vs DP (0/1).

Exercise

분수 배낭은 왜 가치/무게 정렬 그리디로 최적이 되는데 0/1 배낭은 안 되는지 설명해 봐. 0/1에서 무게당 가치 그리디가 차선이 되는 구체적인 작은 예(아이템 몇 개와 용량)를 들어. 그다음 이 사례가 그리디 vs DP 선택에 대해 보여 주는 일반 규칙을 말해.

Hint

분수 배낭에서는 마지막 남는 공간을 언제나 다음 비율의 아이템 조각으로 채울 수 있어서 비율 최고 우선이 증명 가능하게 최적이야. 0/1의 예: 용량 10에 아이템 (가치 6, 무게 6), (가치 5, 무게 5), (가치 5, 무게 5). 비율 동률을 첫 아이템 쪽으로 깨면 가치 6만 담기지만, 무게 5짜리 둘이면 가치 10이야. 일반 규칙: 그리디에는 greedy-choice 속성이 필요하고, 쪼개기 금지 같은 제약이 그걸 깨면 DP를 써.

갈림길의 질문

배낭: 규칙 하나가 모든 걸 뒤집는다

선택의 비용

피파의 고백

Code

External links

Exercise

Progress

댓글 0