[Python] 알고리즘 개념16 - 그리디 알고리즘(Greedy Algorithm)

 

 

🚀 1. 그리디 알고리즘이란?

**그리디 알고리즘(Greedy Algorithm)**은 매 순간 가장 좋아 보이는 선택(최적해)을 하면서 전체 문제를 해결하는 알고리즘이에요.

 

💡 쉽게 이해하기

• 🍕 피자를 한 조각씩 먹을 때, 가장 맛있는 부분부터 먹는 것!
• 💰 잔돈 거슬러 줄 때, 가장 큰 화폐 단위부터 사용하는 것!
• 📆 회의 일정을 잡을 때, 가장 빨리 끝나는 회의부터 선택하는 것!

 

📌 그리디 알고리즘의 핵심 원칙

1. 탐욕적 선택 속성(Greedy Choice Property): 각 단계에서 최선의 선택을 해도 최적의 해를 얻을 수 있어야 해요.
2. 최적 부분 구조(Optimal Substructure): 부분 문제의 최적해가 전체 문제의 최적해를 구성해야 해요.

➡ 즉, 매 순간 최적의 선택을 하면서 문제를 해결하는 방식이에요!

---

 

 

🚀 2. 그리디 알고리즘을 사용할 수 있는 경우

 

📌 그리디 알고리즘이 올바르게 동작하려면?

• 현재 선택이 앞으로의 선택에 영향을 주지 않아야 해요. (즉, 최적 부분 구조가 있어야 해요!)
• 각 단계에서의 최선의 선택이 전체 문제에서의 최적해를 보장해야 해요. (즉, 탐욕적 선택 속성이 있어야 해요!)

 

📌 그리디 알고리즘이 자주 사용되는 문제 유형

문제 유형 예제

최소 동전 거스름돈	가장 큰 화폐 단위부터 거슬러 주기
회의실 배정	가장 빨리 끝나는 회의부터 선택
배낭 문제 (Fractional Knapsack)	가장 비싼 물건부터 담기
Huffman Coding	데이터 압축 알고리즘

➡ 그리디 알고리즘이 항상 정답을 보장하는 것은 아니지만, 적용 가능한 문제에서는 매우 효율적이에요!

---

 

 

🚀 3. 그리디 알고리즘 구현 예제

 

 

✅ 1) 최소 동전 거스름돈 문제

💡 문제:

거스름돈 n원을 줄 때, 가장 적은 개수의 동전을 사용하세요.

 

📌 그리디 알고리즘 해결 방법

1. 가장 큰 단위의 동전부터 거슬러 준다.
2. 남은 금액을 다시 거슬러 준다.

 

💡 Python 코드 구현

def min_coins(n, coins):
    count = 0
    for coin in coins:
        count += n // coin  # 해당 동전으로 거슬러 줄 수 있는 개수
        n %= coin  # 남은 금액 갱신
    return count

coins = [500, 100, 50, 10]  # 가장 큰 단위부터 정렬
print(min_coins(1260, coins))  # 출력: 6

➡ 500원 2개, 100원 2개, 50원 1개, 10원 1개로 총 6개의 동전이 필요해요!

---

 

 

✅ 2) 회의실 배정 문제

 

💡 문제:

여러 개의 회의 일정이 주어졌을 때, 가장 많은 회의를 할 수 있는 방법을 찾아보세요.

 

📌 그리디 알고리즘 해결 방법

1. 회의를 종료 시간이 빠른 순서로 정렬한다.
2. 가장 빨리 끝나는 회의를 선택하고, 다음 회의를 이어서 선택한다.

 

💡 Python 코드 구현

def max_meetings(meetings):
    meetings.sort(key=lambda x: x[1])  # 종료 시간을 기준으로 정렬
    count = 0
    last_end = 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)]
print(max_meetings(meetings))  # 출력: 4

➡ 그리디하게 종료 시간이 빠른 회의부터 선택하면, 최대한 많은 회의를 진행할 수 있어요!

---

 

 

✅ 3) 배낭 문제 (Fractional Knapsack)

 

💡 문제:

무게 제한이 있는 배낭에 최대한 가치를 높이도록 물건을 담아보세요. (단, 물건을 쪼갤 수 있음)

 

📌 그리디 알고리즘 해결 방법

1. 가치 대비 무게 비율이 높은 물건부터 담는다.
2. 배낭이 가득 찰 때까지 반복한다.

 

💡 Python 코드 구현

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:
            total_value += value
            capacity -= weight
        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. 그리디 알고리즘의 한계

 

📌 그리디 알고리즘이 항상 정답을 보장하지 않는 이유

1. 탐욕적 선택이 전체 최적해가 아닐 수 있어요. (예: 0-1 배낭 문제)
2. 백트래킹이나 동적 프로그래밍(DP)이 필요한 경우가 있어요.
3. 모든 문제에서 적용 가능한 것은 아니에요.

 

💡 그리디가 실패하는 예제: 0-1 배낭 문제

• 물건을 쪼갤 수 없는 경우, 그리디 알고리즘이 최적해를 보장하지 않아요.
• 이 경우 **동적 프로그래밍(DP)**을 사용해야 해요.

➡ 그리디 알고리즘이 적용 가능한 문제인지 먼저 확인하는 것이 중요해요!

---

 

 

✅ 마무리 정리

• 그리디 알고리즘은 매 순간 최적의 선택을 하면서 문제를 해결하는 방법이에요.
• 탐욕적 선택 속성과 최적 부분 구조가 만족될 때 효과적으로 사용할 수 있어요.
• 자주 출제되는 유형: 최소 동전 거스름돈, 회의실 배정, 배낭 문제 등
• 하지만 모든 문제에서 최적해를 보장하는 것은 아니므로 주의해야 해요!