greedy 알고리즘이란 무엇이며 언제 동작하나요?

Question

Accepted Answer

**Greedy(탐욕) 알고리즘**은 각 단계에서 **국소적으로 최적인 선택**을 하여 전역 최적에 이르기를 기대합니다. 단순하고 빠르지만, 문제가 **greedy-choice property(탐욕 선택 속성)**와 **optimal substructure(최적 부분 구조)**를 가질 때만 올바릅니다.

## 개념

과거의 선택을 결코 재고하지 않습니다 — 즉각적인 최선의 선택지에 전념하고 넘어갑니다.

## 예시: 표준 동전으로 거스름돈 만들기

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # 큰 동전부터
        while amount >= coin:
            amount -= coin             # 가능한 한 많이 사용
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

이것은 미국 동전에는 최적이지만, {1, 3, 4} 같은 집합에서는 **실패**합니다. 여기서 greedy는 6에 대해 3+3 대신 4+1+1을 줍니다.

## greedy가 동작하는 경우

- **최적 부분 구조:** 최적해가 최적 부분해를 포함합니다.
- **탐욕 선택 속성:** 국소 최적이 전역 최적의 일부입니다.

동작하는 예시: Dijkstra, Kruskal/Prim(MST), Huffman coding, 구간 스케줄링.

## 복잡도

보통 빠릅니다 — 정렬 후 흔히 O(n log n)입니다.

## 함정

Greedy는 **항상 올바른 것은 아닙니다**. 신뢰하기 전에 탐욕 선택 속성을 증명하거나 brute-force/DP 기준선과 비교해 테스트하세요.

## 왜 중요한가

Greedy가 적용될 때는 DP나 brute force보다 훨씬 단순하고 빠릅니다.

*언제* 유효한지 — 그리고 언제 조용히 틀린 답을 주는지 — 아는 것은 알고리즘적 성숙함의 표시입니다.

많은 핵심 그래프 알고리즘이 본질적으로 greedy입니다.