탐욕법(Greedy Algorithm): 최적해를 빠르게 찾는 기법

🔹 탐욕법이란?

1. 탐욕법(Greedy Algorithm)의 정의

탐욕법(Greedy Algorithm)은 문제를 해결할 때 매 단계에서 가장 최선이라고 판단되는 선택을 반복하여 전체 최적해를 구하는 알고리즘 기법입니다.

✅ 탐욕법의 주요 특징:

• 매 단계에서 가장 최적이라고 생각되는 해를 선택
• 선택 후에는 되돌아가지 않음 (백트래킹 없음)
• 빠르고 단순한 계산으로 문제 해결 가능
• 항상 최적해를 보장하지는 않지만, 특정 문제에서는 유효

📌 탐욕법은 최적해를 구하는 문제뿐만 아니라 근사 해법(Approximation Algorithm)으로도 많이 사용됩니다.

---

🔹 탐욕법의 동작 과정

1. 현재 상태에서 가장 최적의 선택을 결정
2. 선택한 해를 확정하고 다음 단계로 진행
3. 이 과정을 반복하여 전체 문제를 해결
4. 최적해를 도출하거나 근사해를 얻음

✔️ 탐욕법을 활용한 거스름돈 문제 예제 (Python):

# 탐욕법을 이용한 거스름돈 문제 해결

def greedy_change(coins, amount):
    coins.sort(reverse=True)  # 큰 금액의 동전부터 사용
    result = {}

    for coin in coins:
        count = amount // coin
        amount -= count * coin
        result[coin] = count

    return result

coins = [500, 100, 50, 10]
amount = 870
print(greedy_change(coins, amount))  # 출력: {500: 1, 100: 3, 50: 1, 10: 2}

📌 탐욕법을 사용하면 빠르게 해를 구할 수 있습니다.

---

🔹 탐욕법 vs 최적해 비교

✔️ 탐욕법이 항상 최적해를 보장하는 것은 아님

• 일부 문제에서는 최적해를 보장하지만, 일부 문제에서는 근사해만 가능
• 동적 계획법(DP)이나 백트래킹 기법이 필요한 경우도 존재

✔️ 탐욕법이 최적해를 보장하는 문제 예시

• 거스름돈 문제 (동전이 배수 관계일 경우)
• 최소 신장 트리(MST) 문제 (크루스칼 알고리즘, 프림 알고리즘)
• 활동 선택 문제(Activity Selection Problem)

✔️ 탐욕법이 최적해를 보장하지 않는 문제 예시

• 배낭 문제(Knapsack Problem) (Fractional Knapsack은 탐욕법 가능하지만 0/1 Knapsack은 DP 필요)
• 최단 경로 문제(Shortest Path Problem) (다익스트라 알고리즘은 특정 조건에서만 탐욕법 적용 가능)

📌 탐욕법이 유효한지 여부는 문제의 특성에 따라 다릅니다.

---

🔹 탐욕법이 사용되는 문제 유형

1. 최단 경로 문제

✅ 다익스트라 알고리즘 (Dijkstra’s Algorithm)
✔️ 음수 가중치가 없을 때 탐욕법으로 해결 가능

2. 최소 신장 트리(MST) 문제

✅ 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘
✔️ 탐욕법을 적용하여 최적해 보장

3. 배낭 문제(Fractional Knapsack Problem)

✅ 부분적으로 아이템을 선택할 수 있는 경우 탐욕법이 최적해 보장
✔️ 하지만 0/1 Knapsack 문제는 동적 계획법 필요

4. Huffman 코딩(Huffman Coding)

✅ 데이터 압축을 위한 최적의 접두사 코드(prefix code) 생성
✔️ 탐욕법을 사용하여 최적해를 보장

📌 탐욕법이 유효한 문제에서는 매우 빠르고 효율적인 해결책을 제공합니다.

---

🔹 탐욕법과 동적 계획법 비교

기법	방식	사용 사례
탐욕법(Greedy Algorithm)	매 단계에서 최적의 선택을 수행	거스름돈 문제, MST, 다익스트라
동적 계획법(Dynamic Programming)	이전 계산을 저장하고 최적해를 구축	배낭 문제, LCS, 최단 경로 문제

📌 탐욕법은 단순하고 빠르지만, 항상 최적해를 보장하지는 않습니다.

---

📌 결론

✅ 탐욕법(Greedy Algorithm)은 매 단계에서 최적의 선택을 하여 문제를 해결하는 기법입니다.
✅ 일부 문제에서는 최적해를 보장하지만, 일부 문제에서는 근사해만 제공할 수 있습니다.
✅ 빠르고 구현이 간단하며, 최적해가 보장되는 문제에서는 매우 효과적입니다.
✅ 동적 계획법, 백트래킹과 비교하여 적용할 문제를 신중히 선택해야 합니다.