"그리디는 가장 유혹적인 패러다임이야: 지금 제일 좋아 보이는 옵션을 잡고 절대 안 돌아봐. 가끔 그게 증명 가능하게 최적. 종종 자신만만하게, 조용히 틀려 — 그리고 위험은 정확히 그게 맞아 보인다는 거야."
그리디 수
그리디 알고리즘은 이 순간 제일 좋아 보이는 선택을 반복해 하고, 헌신하고, 절대 재고 안 해 해법을 지어. 빠르고, 단순하고, 거의 메모리를 안 써. 함정: 이게 특별한 구조 — 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)])) # 3
# 가장 일찍 끝나면 나중 회의에 가장 많은 공간을 남겨 — 그리고 이 국소
# 선택이 늘 전역 최적이란 증명 (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.