[Algorithm] Greedy (그리디 알고리즘)

그리디 알고리즘 (탐욕 알고리즘)

그리디 알고리즘은 매 단계에서 가장 최적이라고 판단되는 선택(Local Optimal Solution)을 반복하여 최종적으로 전체 문제의 최적해(Global Optimal Solution)를 구하는 기법

→   가장 좋은 선택을 하는 방식으로 동작하며 최적해를 보장하는 경우가 많다.

---

그리디 알고리즘의 조건

1. Greedy Choice Property (탐욕적 선택 속성)
   • 현재 단계에서의 최적 선택(전체적인 최적해)이 이후 단계에서도 최적 선택이 되어야 한다.
2. Optimal Substructure (최적 부분 구조)
   • 문제를 작은 부분 문제로 나누었을 때, 각 부분 문제의 최적해를 모아서 전체 문제의 최적해를 구성할 수 있어야 한다.

---

예제

 

1.  거스름돈 문제 (동전 최소 개수)

거스름돈을 줄 때, 동전의 개수를 최소화하도록 주어야 한다. 단, 동전의 단위는 (500, 100, 50, 10)원이라고 가정한다.

 

풀이 방식

1. 가장 큰 단위의 동전부터 최대한 사용한다.
2. 남은 금액에 대해 다시 같은 과정을 반복한다.

시간 복잡도

• O(k)    *k : 동전의 개수

def greedy_coins(amount):
    coins = [500, 100, 50, 10]  # 큰 단위부터 정렬된 동전 리스트
    count = 0

    for coin in coins:
        count += amount // coin  # 해당 동전으로 최대한 사용
        amount %= coin  # 남은 금액 계산

    return count

print(greedy_coins(1260))  # 6

 

---

2.  회의실 배정 문제

여러 개의 회의가 주어질 때, 한 개의 회의실에서 최대한 많은 회의를 진행하려고 한다.
단, 각 회의는 시작 시간과 종료 시간이 있으며, 회의가 겹치면 안 된다.

 

풀이 방식

1. 종료 시간이 빠른 회의를 우선 선택한다.
2. 종료 시간 이후에 시작하는 회의 중 가장 빠른 회의를 선택한다.
3. 이를 반복한다.

시간 복잡도

• 정렬 : O(N log N)
• 회의 선택 과정 : O(N)
• 시간 복잡도 : O(N log N)

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

    for start, end in meetings:
        if start >= last_end_time:  # 현재 회의가 이전 회의 이후에 시작되면 선택
            count += 1
            last_end_time = end

    return count

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

 

---

Greedy vs. Dynamic Programming (DP)

비교 항목 Greedy 알고리즘 Dynamic Programming (DP)

비교 항목	그리디	다이나믹 프로그래밍
방법	현재 최적의 선택을 반복	부분 문제를 저장하고 활용
속도	일반적으로 빠름 (O(N log N) 이하)	느림 (O(N^2) 또는 O(N^3))
조건	탐욕적 선택 속성, 최적 부분 구조를 만족해야 함	최적 부분 구조, 중복 부분 문제를 만족해야 함
예제	거스름돈 문제, 회의실 배정 문제, 크루스칼 알고리즘 (MST)	피보나치 수열, 배낭 문제, 최단 경로 문제 (플로이드-워셜)