💰 그리디 알고리즘 (Greedy Algorithm) 완전 정리

개념 / 적용 조건 / 실전 예제 / DP와 비교

---

✅ 그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm)은
현재 상황에서 가장 좋아 보이는 선택을 반복적으로 수행하여
전체 문제의 최적해를 찾는 알고리즘이다.

❗ '지금 당장' 최적인 선택이
'전체적으로도' 최적인 결과를 보장할 때만 정답이 된다.

---

✅ 언제 그리디 알고리즘을 쓸 수 있을까?

항상 정답이 되려면 아래 두 가지 조건을 만족해야 한다.

1️⃣ 탐욕 선택 속성 (Greedy Choice Property)

• 현재 선택이 이후에 영향을 주지 않음
• 매 순간 가장 최선의 선택을 해도 전체 최선이 보장됨

2️⃣ 최적 부분 구조 (Optimal Substructure)

• 문제의 전체 최적해가
  하위 문제의 최적해를 조합해서 만들 수 있음

✔ 둘 다 만족할 때 → 그리디로 풀 수 있음

---

✅ 대표적인 예제

📌 예제 1: 거스름돈 (동전 최소 개수)

500원, 100원, 50원, 10원짜리 동전이 있을 때  
거스름돈을 가장 적은 수의 동전으로 바꿔라

coins = [500, 100, 50, 10]
n = 1260
count = 0

for coin in coins:
    count += n // coin
    n %= coin

print(count)  # 6 (500x2 + 100x2 + 50x1 + 10x1)

✔️ 큰 동전부터 사용하는 것이 항상 최적이라는 보장이 있음 → 그리디 가능
❗ 동전 종류가 400원, 300원, 100원 이런 식이면? → 그리디 불가능 (DP 필요)

📌 예제 2: 회의실 배정 (백준 1931)

N개의 회의가 있고, 각 회의의 시작/끝 시간이 주어짐  
최대 몇 개의 회의를 겹치지 않고 배정할 수 있을까?

• 종료 시간이 빠른 회의를 먼저 선택하는 것이 핵심

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10)]
meetings.sort(key=lambda x: (x[1], x[0]))  # 종료 시간 기준 정렬

end_time = 0
count = 0
for start, end in meetings:
    if start >= end_time:
        count += 1
        end_time = end

print(count)

✔️ 매 순간 가장 빨리 끝나는 회의를 선택 → 그리디 전략

📌 예제 3: 최소 회의실 수 (강의실 문제, 백준 11000)

• 시작/종료 시간이 겹치지 않게 회의실을 배정하되
  필요한 최소 회의실 개수를 구하는 문제

✔️ 이건 우선순위 큐 (heapq)를 활용한 Greedy + 자료구조 문제다!

---

✅ DP와의 차이점은?

항목	그리디	DP
선택 기준	지금 가장 좋아 보이는 것	모든 경우를 고려하며 누적
계산 방식	한 방향으로만 진행	중복 계산을 막고 누적
메모리	적음	테이블/메모 필요
정답 보장	구조적으로 보장될 때만	항상 보장됨 (올바른 설계 시)
예시	동전 거스름돈, 회의실 배정	피보나치, 배낭 문제, 1로 만들기

---

✅ 실전 문제에서의 그리디 판단법

• 선택 순간에 가장 좋아 보이는 걸 "확정"해도 되는가?
• 지금의 결정이 이후에 영향을 주지 않는가?
• 가능한 행동이 정렬 기준 하나로 정해지는가?
• 완전 탐색/DP 없이도 직관적으로 답이 보이는가?

→ 그렇다면 그리디 알고리즘을 먼저 시도해볼 만하다.

---

📌 그리디처럼 보이지만 실제로는 다른 알고리즘들

그리디처럼 당장 최선의 선택을 반복하는 알고리즘들이 꽤 많지만,
전부 그리디 알고리즘으로 분류되진 않는다.

알고리즘	실제 분류	설명
거스름돈 문제 (단, 배수 관계가 성립할 때)	✅ 그리디	큰 단위 동전부터 선택 → 항상 최적
활동 선택 문제	✅ 그리디	끝나는 시간 빠른 회의를 먼저 고르면 전체 최적
크루스칼 알고리즘 (MST)	✅ 그리디	가장 가중치 작은 간선을 먼저 선택
허프만 코딩	✅ 그리디	가장 빈도 낮은 노드부터 병합
결정 트리 학습	✅ 그리디 기반	각 단계에서 가장 좋은 기준으로 분할 (탐욕적 학습)
다익스트라 알고리즘	❗ 그리디 + 우선순위 큐	가장 가까운 정점부터 방문하지만, 그래프 탐색 알고리즘
프림 알고리즘 (MST)	❗ 그리디 + 그래프 구조	연결된 정점 중 가장 짧은 간선을 선택 (우선순위 큐 활용)

탐욕적인 선택을 하더라도, 그게 전체 최적해를 보장하는 구조여야 "진짜 그리디"라고 할 수 있다.

---

🎯 마무리 요약

• 그리디 알고리즘은 당장 최적의 선택을 반복하여 전체 해를 구성하는 방식이다.
• 항상 정답을 보장하지는 않으며,
  탐욕 선택 속성과 최적 부분 구조가 모두 있어야 적용 가능하다.
• 구조가 명확하면 빠르고 간단하게 풀 수 있어
  실전에서 DP보다 더 빨리 정답에 도달할 수 있는 경우도 많다.
• 겉보기엔 그리디처럼 보이지만, 다익스트라 / 프림처럼
  내부적으로 그래프 구조, 우선순위 큐, 탐색 로직을 사용하는 알고리즘은
  진짜 그리디와는 구분해서 이해해야 한다.