그리디 알고리즘 (Greedy Algorithm)

📌 개요

그리디 알고리즘(Greedy Algorithm)은 매 순간 최적이라고 생각되는 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다.
일반적으로 "탐욕적 기법" 이라고도 하며, 지역적으로 가장 좋은 선택을 하면 결국 전체적으로도 최적의 해를 구할 수 있다는 가정을 기반으로 합니다.

✅ 그리디 알고리즘의 핵심 개념

• 현재 단계에서 최선의 선택을 하면 전체적으로도 최선이 될 것이라는 가정
• 결과적으로 전체 최적해(Optimal Solution)에 도달할 수 있어야 함
• 일반적으로 정렬(Sorting)과 함께 사용되는 경우가 많음

---

📌 그리디 알고리즘의 특징

✅ 장점

• 빠른 실행 속도 → 보통 O(N log N) 이하의 복잡도를 가짐 (정렬이 필요한 경우 O(N log N))
• 단순한 구현 → 단계별로 최선의 선택을 하기 때문에 코드가 직관적

❌ 단점

• 항상 최적해(Optimal Solution)를 보장하지는 않음 → 문제의 특성에 따라 정답이 아닐 수도 있음
• DP(Dynamic Programming)보다 범용성이 떨어짐 → DP는 최적 부분 구조와 중복 부분 문제를 활용할 수 있지만, 그리디는 모든 문제에 적용할 수 없음

---

📌 그리디 알고리즘이 적용 가능한 조건

그리디 알고리즘을 사용할 수 있는 문제는 "탐욕적 선택 속성(Greedy Choice Property)" 과 "최적 부분 구조(Optimal Substructure)" 를 만족해야 합니다.

1. 탐욕적 선택 속성(Greedy Choice Property)
   • 각 단계에서 지역적으로 최적의 선택을 해도 전체 문제의 최적해를 보장할 수 있어야 함
2. 최적 부분 구조(Optimal Substructure)
   • 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구할 수 있어야 함

✅ 예제 문제: "동전 거스름돈 문제"
✅ 예제 문제: "회의실 배정 문제"

---

📌 그리디 알고리즘 대표 문제 및 코드 예제

1. 동전 거스름돈 문제

💡 문제 설명
어떤 가게에서 손님에게 거스름돈을 줄 때, 가장 적은 개수의 동전을 사용하여 거스름돈을 줄 수 있도록 설계하는 문제입니다.
단, 사용할 수 있는 동전은 큰 단위가 작은 단위의 배수인 경우에만 그리디로 최적해를 보장할 수 있습니다.

🔹 입력 예시:

• 거스름돈: 1260원
• 동전 단위: [500, 100, 50, 10]

🔹 해결 방법:

• 가장 큰 단위의 동전부터 가능한 개수를 사용하여 해결

def min_coins(change):
    coins = [500, 100, 50, 10]  # 큰 단위 동전부터 선택
    count = 0

    for coin in coins:
        count += change // coin  # 해당 동전으로 줄 수 있는 개수
        change %= coin  # 남은 거스름돈 갱신

    return count

print(min_coins(1260))  # 출력: 6

✅ 시간 복잡도: O(N) (동전의 개수에 비례)
✅ 그리디 알고리즘이 항상 최적해를 보장하는 경우: 큰 단위가 작은 단위의 배수 관계일 때

---

2. 회의실 배정 문제 (Greedy Interval Scheduling)

💡 문제 설명
여러 개의 회의가 주어질 때, 한 개의 회의실에서 최대한 많은 회의를 진행하려면 어떻게 해야 할까?
각 회의는 시작 시간과 끝나는 시간이 주어지며, 한 회의가 끝난 이후에 다음 회의를 시작할 수 있습니다.

🔹 입력 예시:

회의 정보: [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]

🔹 해결 방법:

• 끝나는 시간이 가장 빠른 회의를 먼저 선택하면 최대한 많은 회의를 진행할 수 있음
• 회의가 겹치지 않는 조건을 유지하며 선택

def max_meetings(meetings):
    meetings.sort(key=lambda x: x[1])  # 종료 시간을 기준으로 정렬
    count, last_end = 0, 0

    for start, end in meetings:
        if start >= last_end:  # 이전 회의 종료 이후 시작 가능한 경우 선택
            count += 1
            last_end = end  # 종료 시간 업데이트

    return count

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
print(max_meetings(meetings))  # 출력: 4

✅ 시간 복잡도: O(N log N) (정렬 과정이 포함됨)
✅ 탐욕적 선택 속성이 성립하는 이유: 가장 빨리 끝나는 회의를 먼저 선택하면 남은 시간 동안 최대한 많은 회의를 배정할 수 있음

---

3. 배낭 문제 (Fractional Knapsack)

💡 문제 설명
무게 제한이 있는 배낭에 여러 개의 물건을 넣을 때, 최대 가치를 얻도록 물건을 선택하는 문제입니다.
각 물건은 무게(W)와 가치(V)를 가지고 있으며, 분할이 가능하다고 가정합니다.

🔹 해결 방법:

• "가치 대비 무게 비율"이 가장 높은 물건부터 선택
• 분할이 가능하므로 일부만 선택할 수도 있음

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

✅ 시간 복잡도: O(N log N) (정렬 과정이 포함됨)
✅ 탐욕적 선택 속성이 성립하는 이유: 가장 가치 대비 무게 비율이 높은 물건을 선택하면 최대 가치를 얻을 수 있음

---

📌 결론

• 그리디 알고리즘은 빠르고 효율적인 방식이지만, 항상 최적해를 보장하지는 않음
• 탐욕적 선택 속성과 최적 부분 구조를 만족하는 문제에서만 적용 가능
• 대표적인 문제 유형: 거스름돈, 회의실 배정, 배낭 문제, 최소 신장 트리(프림, 크루스칼)

🚀 그리디 알고리즘을 사용할 때는 "최적해를 보장할 수 있는지"를 항상 고민해야 합니다!