그리디(Greedy) 알고리즘은 각 단계에서 지금 가장 좋아 보이는 선택을 반복해 전체 최적해를 찾는 기법이다. 최적 부분 구조와 탐욕 선택 속성이 있을 때 정확한 답을 보장한다.
핵심 조건
| 조건 | 설명 |
|---|
| 탐욕 선택 속성 | 지금의 최선 선택이 전체 최적해에 포함됨 |
| 최적 부분 구조 | 전체 최적해가 부분 문제의 최적해로 구성됨 |
대표 문제
동전 거스름돈
python
def make_change(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count
coins = [500, 100, 50, 10]
print(make_change(coins, 1260)) # 6 (500+500+100+100+50+10)
활동 선택 (Activity Selection)
python
def activity_selection(activities):
# 종료 시간 기준 정렬
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for start, end in activities[1:]:
if start >= selected[-1][1]: # 마지막 선택 종료 후 시작
selected.append((start, end))
return selected
그리디 vs DP
| 항목 | 그리디 | 동적 프로그래밍 |
|---|
| 접근 | 현재 최선 선택 | 모든 경우 탐색 |
| 속도 | 빠름 | 상대적으로 느림 |
| 최적 보장 | 조건 만족 시만 | 항상 보장 |
활용 사례
참고문헌
- •Cormen et al. Introduction to Algorithms — Chapter 16
