dynamic programming은 greedy와 비교해 언제 적용되나요?

Question

Accepted Answer

DP와 greedy 모두 **최적 부분 구조(optimal substructure)**가 필요합니다. 차이는 이렇습니다. **greedy**는 추가로 **greedy-choice property(탐욕 선택 속성)**(국소 최적이 전역 최적임)를 요구하는 반면, **DP**는 **여러 선택지와 겹치는 부분 문제**를 고려해야 할 때 필요합니다.

## 구별

```text
최적 부분 구조가 있는가?  -- 둘 다 필요
  + 탐욕 선택 속성이 성립하는가?  -> GREEDY (빠름, 선택의 한 번 순회)
  + 여러 부분해를 비교해야 / 겹치는가?  -> DYNAMIC PROGRAMMING
```

## 전형적 대비: 거스름돈 만들기

```python
# 동전 {1,3,4}, 금액 6에 대해 greedy 실패 -> 4+1+1 (동전 3개)
# DP는 진짜 최적을 찾음: 3+3 (동전 2개)
def min_coins(amount, coins):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)  # 모든 동전을 시도
    return dp[amount]

min_coins(6, [1, 3, 4])               # -> 2
```

Greedy는 하나의 선택에 전념하고, DP는 모두 탐색하여 최선을 유지합니다.

## 각각의 적용 시점

- **Greedy:** 구간 스케줄링, Huffman, Dijkstra, MST — 입증된 탐욕 선택 속성.
- **DP:** knapsack, edit distance, 일반 거스름돈 만들기 — 선택들이 상호작용.

## 복잡도

Greedy는 보통 O(n log n)이고, DP는 정확성을 위해 더 많은 시간/공간(흔히 O(n·m))을 맞바꿉니다.

## 함정

속성을 증명하지 않고 greedy를 사용하면 작은 테스트는 통과하지만 **틀린 답**을 줍니다. 의심스러우면 DP를 사용하거나 brute force와 비교해 greedy를 검증하세요.

## 왜 중요한가

greedy가 유효할 때 그것을 고르면 엄청난 시간을 절약하고, 유효하지 않을 때 고르면 조용한 버그를 만듭니다.

어느 패러다임이 맞는지 아는 것 — 그리고 그것을 증명할 수 있는 것 — 은 시니어 수준의 구별점입니다.

DP로 인한 과잉 설계와 부적절한 greedy 선택으로 인한 미달 둘 다를 막아 줍니다.