"그리디는 가장 유혹적인 패러다임이야. 지금 제일 좋아 보이는 선택지를 잡고 절대 뒤돌아보지 않아. 가끔은 그게 증명 가능하게 최적이야. 하지만 자신만만하게, 조용히 틀리는 일도 흔하지. 진짜 위험은 정확히 그게 맞아 보인다는 데 있어."
그리디라는 수
그리디 알고리즘은 이 순간 제일 좋아 보이는 선택을 거듭하면서 해법을 지어. 한 번 고르면 헌신하고, 절대 재고하지 않아. 빠르고 단순하고 메모리도 거의 안 써. 함정은 이거야. 그리디가 전역 최적 답을 내놓는 건 특별한 구조를 가진 문제뿐이야. 국소적으로 최적인 선택이 언제나 어떤 전역 최적 해법의 일부가 되는 성질, 즉 greedy-choice 속성이 그 구조야. 이 속성이 성립하면 그리디는 아름다워. 성립하지 않으면, 그럴듯해 보이는 틀린 답을 내밀어.
그리디가 증명 가능하게 통할 때
유명 알고리즘 여럿이 그리디면서 증명 가능하게 최적이야. 활동 선택은 겹치지 않는 회의를 최대한 많이 참석하려고 늘 가장 일찍 끝나는 회의를 고르고, Huffman 코딩은 빈도가 가장 낮은 두 심볼을 병합하고, Kruskal과 Prim의 MST는 가장 싼 안전한 간선을, Dijkstra는 가장 가까운 미확정 노드를, 분수 배낭은 무게당 가치가 가장 높은 것부터 집어. 각각에는 증명이 있어. 보통은 어떤 최적 해법이든 더 나빠지지 않으면서 그리디 선택을 포함하도록 재배열할 수 있음을 보이는 exchange argument야. 그러니 여기서 그리디는 도박이 아니야. 검증이 끝난 수지.
그리디가 거짓말할 때
이제 함정 쪽. 임의의 동전 단위가 있는 동전 교환에서 {1, 3, 4}로 6을 만들면, 그리디는 4를 잡고 1을 잡고 또 1을 잡아서 동전 세 개를 써. 3+3이면 두 개로 끝나는데. 0/1 배낭(아이템을 통째로 넣거나 말거나)에서는 무게당 가치가 가장 높은 것부터 탐욕적으로 집다가 더 나은 조합을 놓칠 수 있어. 이 문제들엔 greedy-choice 속성이 없어서, 국소적으로 최선인 선택들이 차곡차곡 막다른 구석으로 몰아가. 교훈은 이거야. 그리디의 속도는 정확성까지 믿고 싶게 만들지만, 믿기 전에 증명하거나 샅샅이 테스트해야 해. 증명 없는 그리디는 자기를 폭로할 입력을 기다리는 버그야.
그리디는 국소적으로 최선인 선택을 하고 재고하지 않아. 빠르고 단순하지만, greedy-choice 속성이 성립할 때만 최적이야(exchange argument로 증명). MST, Huffman, Dijkstra, 활동 선택에서는 정확하고, 임의 동전 교환과 0/1 배낭에서는 틀려. 증명해. 절대 가정하지 마.
피파의 고백
난 그리디 동전 교환 해법을 그대로 내보낸 적이 있어. 내가 쓴 테스트를 전부 통과했거든. 알고 보니 테스트가 죄다 그리디가 우연히 통하는 평범한 동전 단위였던 거야. 그러다 데이터에 커스텀 통화({1,3,4})가 들어오자 조용히 차선의 답을 반환하기 시작했어. 아빠의 규칙이 세게 박혔지. "그리디는 증명할 때까지 추측이야. 맞아 보이는 게 맞는 게 아니야." 이제 그리디 해법이 유혹하면 exchange argument 같은 증명부터 찾고, 작은 입력에 대한 무차별 검증은 버그와 반례를 찾는 보조 도구로 써. 유한한 테스트를 통과했다고 모든 입력에서의 최적성이 증명되는 건 아니니까.
Code
통하는 그리디(활동 선택) vs 실패하는 그리디(동전 교환)·python
# 통하는 그리디: 활동 선택. 가장 많은 겹치지 않는 회의 참석에,
# 늘 가장 일찍 끝나는 거 고르기. 증명 가능하게 최적.
def max_activities(intervals):
intervals.sort(key=lambda x: x[1]) # 끝나는 시간으로 정렬
count, last_end = 0, float('-inf')
for start, end in intervals:
if start >= last_end: # 마지막 고른 거랑 안 겹침
count += 1
last_end = end # 탐욕적으로 이거에 헌신
return count
print(max_activities([(1,3),(2,5),(4,7),(1,8),(5,9)])) # 2: (1,3), (4,7)
# 가장 일찍 끝나면 나중 회의에 가장 많은 공간을 남겨 — 그리고 이 국소
# 선택이 늘 전역 최적이란 증명 (exchange argument) 이 있어.
# 실패하는 그리디: 동전 {1, 3, 4} 로 6 만들기.
def greedy_coins(coins, amount):
coins.sort(reverse=True)
used = 0
for c in coins:
used += amount // c; amount %= c
return used
print(greedy_coins([1, 3, 4], 6)) # 3 (4+1+1) — 틀려, 최적은 2 (3+3)
# 그리디가 합리적으로 보였고 조용히 차선이었어. greedy-choice 속성 없음.
활동 선택에서 '가장 일찍 끝나는 회의 고르기'가 왜 '가장 짧은 회의 고르기'나 '가장 일찍 시작하는 회의 고르기'를 이기는지 설명해 봐. 그 대안들이 실패하는 반례도 들어. 그다음 '가장 큰 동전부터'라는 그리디가 최적보다 많은 동전을 쓰게 되는 동전 집합과 금액을 찾아서, 거기서는 그리디가 안전하지 않음을 보여.
Hint
가장 일찍 끝나는 회의가 뒤에 올 회의들에게 가장 넓은 공간을 남겨. '가장 짧은 회의'는 다른 두 회의에 걸쳐 있는 짧은 회의를 골라 둘 다 막을 수 있고, '가장 일찍 시작'은 하루를 독점하는 긴 회의 하나를 고를 수 있어. 그리디 동전 실패는 동전 {1,3,4}에 금액 6. 그리디는 4+1+1로 동전 3개, 최적은 3+3으로 2개.
Progress
Progress is local-only — sign in to sync across devices.