그리디(Greedy) 알고리즘은 전체를 한 번에 고려하지 않고,
매 단계마다 지금 당장 가장 좋아 보이는 선택을 반복해서 문제를 푸는 방식이다.
계산이 빠르고 구현이 단순하지만, 문제에 따라 전역 최적해를 보장하지 못할 수도 있다.
아래 두 가지 예제로 "그리디가 통하는 경우"와 "그리디가 실패하는 경우"를 직접 비교해 보자.
🪙 예제 1 — 거스름돈 문제 Coin Change
380원
그리디가 사용한 동전 수—
DP로 구한 최소 동전 수—
동전 종류를 고르고 "그리디 실행"을 눌러보세요.
🐍 그리디 거스름돈 코드
defgreedy_coin_change(amount, coins):
coins = sorted(coins, reverse=True) # 큰 동전부터
used = []
for c in coins:
while amount >= c:
used.append(c)
amount -= c # 지금 쓸 수 있는 가장 큰 동전만 선택return used # 표준 화폐(500,100,50,10)에서는 항상 최소 개수# 하지만 (4,3,1) 같은 화폐에서는 최소가 아닐 수 있음!
📅 예제 2 — 활동 선택 문제 항상 최적 보장
회의실 하나로 겹치지 않게 최대한 많은 활동을 진행하려면? 그리디 전략은 간단하다 —
가장 일찍 끝나는 활동부터 순서대로 확인하며, 이미 선택한 활동과 겹치지 않으면 선택한다.
이 문제는 그리디가 항상 최적해를 보장하는 대표 사례다.
02468101214
선택된 활동 수 (겹치지 않음)—
🧭 정리 — 그리디가 통할 때 vs 실패할 때
항상 최적 보장
활동 선택 문제, 크루스칼/프림 최소 신장 트리, 다익스트라 최단 경로, 분수 배낭 문제처럼
"부분 문제에서 그리디 선택이 전체 최적해에 포함됨"이 수학적으로 증명되는 경우.
최적 보장 실패
비표준 화폐 거스름돈, 0/1 배낭 문제(쪼갤 수 없는 물건)처럼 당장의 최선이 전체 최적을
해치는 경우. 이때는 모든 경우를 비교하는 동적 계획법(DP)이 필요하다.