python - 탐욕법, 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘 (Greedy Algorithm)

개념

그리디 알고리즘은 현재 시점에서 가장 최선의 선택(최적해)을 반복적으로 수행하여 문제를 해결하는 방법입니다.
이 방법은 특정 조건에서만 전체 문제의 최적해를 보장합니다.

---

1. 그리디 알고리즘의 특징

• 탐욕적 선택 속성:
  각 단계에서의 최선의 선택이 전체 문제의 최적해를 보장해야 합니다.
• 최적 부분 구조:
  문제의 최적해는 부분 문제들의 최적해로 구성될 수 있어야 합니다.
• 간단하고 빠름:
  일반적으로 시간 복잡도가 낮으며, 직관적인 풀이가 가능합니다.
• 최적해 보장 여부:
  모든 문제에서 그리디 알고리즘이 최적해를 보장하지는 않습니다. 문제의 성질을 반드시 확인해야 합니다.

---

2. 그리디 알고리즘의 동작 과정

1. 문제를 여러 단계로 나눔.
2. 각 단계에서 현재 상황에서 최적이라고 판단되는 선택을 함.
3. 이를 반복하여 최종 해를 구성.

---

3. 그리디 알고리즘의 예제

(1) 동전 거스름돈 문제

• 문제: 최소 개수의 동전으로 금액을 거슬러 주기.
• 조건: 동전 단위가 큰 단위가 작은 단위의 배수일 때.

def coin_change(coins, amount):
    coins.sort(reverse=True)  # 동전을 큰 단위부터 정렬
    count = 0
    for coin in coins:
        if amount == 0:
            break
        count += amount // coin  # 해당 동전으로 거슬러 줄 수 있는 개수
        amount %= coin  # 남은 금액 갱신
    return count

coins = [1, 5, 10, 50, 100, 500]
amount = 1260
print(coin_change(coins, amount))  # 출력: 6

 

과정:
500원 2개, 100원 2개, 50원 1개, 10원 1개 → 총 6개.

---

(2) 활동 선택 문제

• 문제: 시작 시간과 종료 시간이 주어진 활동 중, 겹치지 않는 가장 많은 활동을 선택.
• 조건: 종료 시간이 빠른 순서로 선택.

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])  # 종료 시간을 기준으로 정렬
    selected = []
    last_end_time = 0

    for start, end in activities:
        if start >= last_end_time:
            selected.append((start, end))
            last_end_time = end
    return selected

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
print(activity_selection(activities))  # 출력: [(1, 4), (5, 7), (8, 11), (12, 14)]

---

(3) 배낭 문제 (Fractional Knapsack Problem)

• 문제: 무게 제한이 있는 배낭에 물건을 넣을 때, 가치가 최대가 되도록 선택.
• 조건: 물건을 쪼갤 수 있음 (부분적으로 선택 가능).

def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x[1] / x[0], reverse=True)  # 무게당 가치 기준으로 정렬
    total_value = 0
    for weight, value in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += value * (capacity / weight)
            break
    return total_value

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

---

4. 그리디 알고리즘의 장단점

장점

• 빠르고 직관적:
  구현이 쉽고 간단한 문제에서는 매우 효율적입니다.
• 적은 시간 복잡도:
  정렬과 반복문을 사용해 O(N log N) 시간 안에 해결 가능한 경우가 많습니다.
• 다양한 문제에 적용 가능:
  동전 문제, 활동 선택 문제, 배낭 문제 등 여러 유형의 문제에서 활용됩니다.

단점

• 최적해 보장 불가:
  항상 최적해를 보장하지 않으며, 특정 문제에서는 그리디 알고리즘이 비효율적일 수 있습니다.
  • 예: 물건을 쪼갤 수 없는 배낭 문제(0/1 Knapsack Problem).
• 문제의 성질 확인 필요:
  탐욕적 선택 속성과 최적 부분 구조를 만족하는 문제에만 적용 가능.