탐욕 알고리즘

탐욕 알고리즘(Greedy Algorithm)은 문제를 해결할 때, 매 단계에서 가장 최적이라고 판단되는 선택(탐욕적 선택)을 하는 방식으로 동작하는 알고리즘 설계 기법이다. 이 알고리즘은 전역 최적해를 구하기 위해 지역 최적해를 반복적으로 선택하며, 최종적으로 전체 문제의 최적해를 도출하려고 한다.

---

탐욕 알고리즘의 특징

1. 탐욕적 선택(Greedy Choice):
   • 현재 상태에서 가장 최적인 선택을 한다.
   • 미래의 결과를 고려하지 않고, 지금의 선택이 전체적으로도 최적일 것이라고 가정한다.
2. 최적 부분 구조(Optimal Substructure):
   • 문제를 작은 부분 문제로 나눌 수 있어야 하며, 각 부분 문제의 최적해가 전체 문제의 최적해를 보장해야 한다.
3. 단순성과 속도:
   • 동적 프로그래밍과 같은 복잡한 알고리즘에 비해 설계와 구현이 간단하며 빠르게 동작한다.

---

탐욕 알고리즘의 작동 방식

1. 문제를 가능한 여러 단계로 나눈다.
2. 각 단계에서 가장 최적인 선택을 한다.
3. 모든 단계에서 선택이 끝나면 문제의 해를 구한다.

---

탐욕 알고리즘이 적용될 조건

탐욕 알고리즘은 모든 문제에 적용되지 않는다. 다음 두 가지 조건을 만족해야 올바른 해를 구할 수 있다.

1. 탐욕적 선택 속성:
   • 현재 단계에서의 최적 선택이 이후 단계에서도 영향을 미치지 않고 전역 최적해를 보장해야 한다.
2. 최적 부분 구조:
   • 부분 문제의 최적해가 결합되어 전체 문제의 최적해를 구성해야 한다.

---

탐욕 알고리즘의 장단점

장점

• 구현이 간단하고 계산 속도가 빠르다.
• 일부 문제에서는 효율적으로 최적해를 구할 수 있다.
• 메모리 사용량이 적다.

단점

• 모든 경우에 최적해를 보장하지는 않는다.
• 문제의 특성을 분석하지 않고 사용하면 잘못된 결과를 도출할 수 있다.

---

탐욕 알고리즘의 예제

1. 동전 거스름돈 문제

• 문제: 특정 금액을 거슬러 주기 위해 필요한 동전의 최소 개수를 구하라.
• 알고리즘:
  1. 가장 큰 동전부터 사용한다.
  2. 남은 금액에 대해 반복한다.

def greedy_coin_change(coins, amount):
    # coins: 동전 종류 (내림차순 정렬)
    # amount: 거슬러 줄 금액
    coins.sort(reverse=True)  # 동전을 큰 금액부터 정렬
    result = []  # 선택한 동전 목록
    for coin in coins:
        while amount >= coin:
            amount -= coin  # 해당 동전 사용
            result.append(coin)  # 사용한 동전 기록
    return result

# 예제
coins = [500, 100, 50, 10]
amount = 870
print(greedy_coin_change(coins, amount))  # [500, 100, 100, 100, 50, 10, 10]

---

2. 활동 선택 문제(Activity Selection Problem)

• 문제: 서로 겹치지 않는 최대한의 활동을 선택하라.
• 알고리즘:
  1. 활동을 종료 시간이 빠른 순서로 정렬한다.
  2. 각 활동을 선택할 때, 이전 활동과 겹치지 않는 경우만 선택한다.

def activity_selection(activities):
    # activities: (시작 시간, 종료 시간) 리스트
    activities.sort(key=lambda x: x[1])  # 종료 시간이 빠른 순서로 정렬
    selected = [activities[0]]  # 첫 번째 활동 선택
    for i in range(1, len(activities)):
        if activities[i][0] >= selected[-1][1]:  # 이전 활동의 종료 이후 시작
            selected.append(activities[i])
    return selected

# 예제
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print(activity_selection(activities))  # [(1, 4), (5, 7), (8, 9)]

---

3. 배낭 문제(Knapsack Problem, 분수형)

• 문제: 제한된 무게의 배낭에 물건을 담아 최대 가치를 얻어라. (물건을 쪼갤 수 있음)
• 알고리즘:
  1. 물건을 무게 대비 가치가 높은 순으로 정렬.
  2. 배낭에 가능한 최대한 담는다.

def fractional_knapsack(items, capacity):
    # items: (가치, 무게) 리스트
    items.sort(key=lambda x: x[0]/x[1], reverse=True)  # 무게 대비 가치가 높은 순으로 정렬
    total_value = 0  # 총 가치
    for value, weight in items:
        if capacity >= weight:
            capacity -= weight  # 전체를 담을 수 있으면 담는다
            total_value += value
        else:
            total_value += value * (capacity / weight)  # 일부만 담는다
            break
    return total_value

# 예제
items = [(60, 10), (100, 20), (120, 30)]  # (가치, 무게)
capacity = 50
print(fractional_knapsack(items, capacity))  # 240.0

---

탐욕 알고리즘의 활용 사례

1. 최단 경로 문제(Dijkstra 알고리즘):
   • 특정 정점에서 다른 모든 정점까지의 최단 경로 계산.
   • 탐욕적 선택 속성: 현재까지 최단 경로를 선택.
2. 최소 신장 트리 문제(Kruskal 알고리즘, Prim 알고리즘):
   • 그래프에서 최소 비용으로 모든 정점을 연결하는 트리 구성.
3. 허프만 코딩(Huffman Coding):
   • 텍스트 압축에서 사용되는 알고리즘으로, 탐욕적 선택으로 최적의 이진 트리를 생성.