"그리디랑 동적 계획법은 같은 왕좌의 라이벌이야. 배낭 문제가 드라마 전체를 보여줘: 규칙 하나 — 아이템을 쪼갤 수 있어 없어? — 를 바꾸면, 왕관이 그리디에서 DP 로 넘어가."
핵심 결정
그리디랑 DP 둘 다 부분 문제로 해법을 지어, 그래서 어떤 최적화 문제든 자주 갈림길을 마주해: 빠른 그리디 선택으로 넘어갈 수 있나, 아니면 DP 의 샅샅이 탐색에 값을 치러야 하나? 결정 질문은 greedy-choice 속성이 성립하냐 — 국소적으로-최선 옵션에 헌신하는 게 늘 전역-최적 해법을 도달 가능하게 유지하냐? 그렇다면, 그리디 승 (더 빠르고, 단순하고, 테이블 없음). 그리디 선택이 최선 답을 막는 반례가 있으면, DP 가 필요해, 모든 선택을 고려하고 캐시하는. 그리디에 반례 하나만 찾아도 DP 가 필요하다는 증명이야.
배낭: 규칙 하나가 모든 걸 뒤집는다
알고리즘 전체에서 가장 깔끔한 실연. 무게 한계 있는 배낭이랑 무게/값 있는 아이템:
분수 배낭 (아이템 일부를 취할 수 있어): 그리디가 최적. 무게당 값으로 정렬, 최고 비율 먼저 취하고, 다음 아이템이 다 안 맞으면, 맞는 부분만 취해. 증명 가능하게 최적 — 쪼갤 수 있을 때 비율 순서를 못 이겨.
0/1 배낭 (각 아이템 전부-아니면-전무): 그리디 실패, DP 필요. 못 쪼개니까, 최고-비율 아이템 취하기가 더 나은 조합을 밀어낼 수 있어. 고침은 지난 트랙의 2D DP — dp[item][capacity].
같은 아이템, 같은 무게, 같은 목표. '쪼갤 수 있어?' 규칙 하나가 맞는 도구가 한 줄 그리디 정렬이냐 완전한 DP 테이블이냐를 결정해. 그게 패러다임-선택 능력의 축소판이야: 문제 제약의 작은 변화가 어느 전략이 맞는지 뒤집을 수 있어.
greedy-choice 속성 성립하면 그리디 (반례 하나가 반증 → DP). DP 는 모든 선택 시도하는 안전하고 느린 대비책. 제약 하나가 평결을 뒤집어: 분수 배낭은 그리디; 0/1 배낭 (쪼개기 없음) 은 DP 필요. 목표만이 아니라 제약을 읽어.
선택의 비용
DP 가 안전한데 왜 늘 안 써? 그리디가, 유효할 때, 극적으로 더 싸니까 — 분수 배낭은 정렬에 O(n log n) 대 0/1 의 O(n × capacity) 테이블, 그리고 그리디는 O(1) 추가 공간 대 DP 의 테이블. 그리디가 증명 가능하게 정확할 때, DP 에 값 치르는 건 낭비야. 그래서 판단이 진짜고 양방향: 증명 안 된 그리디 믿지 마 (지난 lesson), 근데 증명된 그리디면 될 때 무거운 DP 손대지 마. 능력은 패러다임을 문제의 실제 구조에 맞추는 거야.
피파의 고백
난 '배낭은 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).
분수 배낭이 왜 그리디 (값/무게 정렬) 로 최적 해결되는데 0/1 배낭은 안 되는지 설명해. 0/1 에서 그리디 무게당-값 선택이 차선인 구체적 작은 예 (아이템 몇 개랑 용량) 를 줘. 그다음 이게 그리디 vs DP 고르기에 대해 실연하는 일반 규칙을 말해.
Hint
분수: 마지막 조각을 늘 차선 비율로 채울 수 있어, 그래서 최고-비율-먼저가 증명 가능하게 최적. 0/1 예: 용량 10, 아이템 (값 6, 무게 6) 이랑 (값 5, 무게 5) 둘 — 그리디가 비율-1.0 아이템 (6) 취하는데 무게-5 둘이 10 줘. 규칙: 그리디는 greedy-choice 속성 필요; 제약 (쪼개기 없음) 이 깨면, DP 써.
Progress
Progress is local-only — sign in to sync across devices.