그리디(Greedy) 알고리즘

개요

그리디(Greedy) 알고리즘은 문제 해결 과정에서 매 순간 가장 좋아 보이는 선택(최적의 선택)을 하는 전략이다. 각 단계의 선택이 이후의 선택에 영향을 주지 않는 문제, 즉 **탐욕적 선택 속성(Greedy Choice Property)**과 **최적 부분 구조(Optimal Substructure)**를 만족하는 문제에 효과적이다. 빠르고 구현이 간단하며, 다양한 최적화 문제에서 널리 활용된다.

---

1. 개념 및 정의

그리디 알고리즘의 핵심은 다음과 같다:

• 현재 단계에서 가장 이득이 크거나 비용이 적은 선택을 한다.
• 과거의 선택과 무관하게 현재 선택이 전체 최적해에 포함된다고 가정한다.
• 전체 문제를 한 번의 탐색으로 해결할 수 있다.

단점은 항상 최적의 해를 보장하지 않는다는 것이다.

---

2. 알고리즘 동작 구조

단계	설명
1	문제를 구성 요소로 나눈다
2	현재 가능한 선택 중 가장 좋은 것을 고른다 (Greedy Choice)
3	선택된 항목을 확정하고 다음 단계로 이동한다
4	전체 선택이 끝날 때까지 반복한다

그리디 알고리즘은 보통 반복문 또는 우선순위 큐로 구현된다.

---

3. 대표 알고리즘 및 문제 예시

알고리즘/문제	설명	사용 전략
거스름돈 문제	가장 큰 단위부터 거슬러주기	큰 동전 우선 선택
회의실 배정	종료 시간이 빠른 회의 우선 배정	우선순위 정렬
Kruskal 최소 신장 트리	간선의 가중치가 낮은 순으로 선택	정렬 + 유니온 파인드
Prim 최소 신장 트리	가까운 노드부터 연결	우선순위 큐
Fractional Knapsack	비율이 가장 높은 물건부터 담기	정렬 + 부분 선택

---

4. 파이썬 간단 구현 예 (거스름돈 문제)

def greedy_change(coins, target):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while target >= coin:
            target -= coin
            count += 1
    return count

# 사용 예시
print(greedy_change([500, 100, 50, 10], 1260))  # 출력: 6

---

5. 시간 및 공간 복잡도

항목	복잡도
시간 복잡도	O(n log n) (정렬 포함) 또는 O(n)
공간 복잡도	O(1) 또는 O(n) (우선순위 큐 사용 시)

정렬 기반 문제는 n log n, 탐욕 선택만 있으면 O(n)에 해결 가능하다.

---

6. 시각적 예시: 회의실 배정 문제

입력: 회의 시작/종료 시간 목록 → (1,4), (3,5), (0,6), (5,7), (8,9), (5,9)

• 종료 시간 기준으로 정렬
• 선택: (1,4) → (5,7) → (8,9) → 최대 3개 회의 가능

---

7. 그리디 vs 동적 프로그래밍

항목	그리디 알고리즘	동적 프로그래밍
접근 방식	현재 최선 선택	모든 경우 비교 후 최선 선택
메모리 사용	적음	높음 (DP 테이블 필요)
적용 문제	최적 부분 구조 + 탐욕 선택 속성	중복 부분 문제 + 최적 부분 구조
예시	회의실 배정, Kruskal, Prim	피보나치, 배낭 문제(0-1 Knapsack)

---

8. 활용 분야

분야	적용 예시
네트워크	최소 비용 네트워크 구성 (MST)
자원 스케줄링	회의실, 강의실, CPU 프로세스 배정
물류/배달	최소 이동거리, 물류 경로 구성
수학 문제 풀이	최소 동전 문제, 최대 이익 선택

---

9. 결론

그리디 알고리즘은 현재 상황에서 가장 좋은 선택을 반복하여 전체 최적해를 추구하는 방식으로, 많은 최적화 문제를 빠르고 간단하게 해결할 수 있다. 단, 항상 최적해를 보장하는 것은 아니므로, 그리디 선택 속성과 최적 부분 구조 조건이 성립하는지 확인하는 것이 중요하다. 알고리즘 문제풀이에서 그리디는 빠르게 풀 수 있는 문제들을 효율적으로 해결하는 강력한 전략이다.