💸 그리디 알고리즘 정복하기

---

1. 그리디 알고리즘이 뭐냐?

"지금 당장 보기엔 제일 좋아 보이는 선택을 하는 알고리즘"
다시 말하면, 매 순간 최선의 선택을 반복하는 방식.

✔️ 간단하지만, 구조 잘못 잡으면 틀릴 수도 있음.

---

2. 언제 쓰는 건데?

다음 두 조건을 만족할 때만 그리디가 통한다:

조건	설명
✅ Greedy Choice Property	매 순간의 최선이 전체적으로도 최선이어야 함
✅ Optimal Substructure	문제를 부분 문제로 쪼개도 성질이 유지돼야 함

쉽게 말해서, 그 순간의 선택이 전체 정답을 깨먹으면 그리디는 못 씀.

---

3. 그리디 vs DP 차이?

구분	그리디	DP
전략	매 순간 최선	전부 고려해서 최적
속도	빠름	느릴 수 있음
정답 보장	항상 되는 건 아님	조건 맞으면 보장됨
예시	동전 거스름돈, 회의실 배정	배낭 문제, 최소 거리, 등등

---

4. 실전 예제

---

🪙 예제 1. 거스름돈 문제 (가장 기본)

1260원을 동전으로 거슬러줄 때, 가장 적은 동전 개수는?

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

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

print(count)  # 출력: 6

✔️ 핵심은 큰 단위부터 먼저 쓰는 것
✔️ 이 문제는 동전 단위가 그리디 조건을 만족하니까 정답 나옴

---

🏢 예제 2. 회의실 배정 (백준 1931)

N개의 회의가 시작/끝 시간이 주어질 때, 겹치지 않게 최대 몇 개까지 배정 가능?

n = int(input())
meetings = [tuple(map(int, input().split())) for _ in range(n)]

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

count = 0
end_time = 0

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

print(count)

✔️ 끝나는 시간이 빠를수록 → 이후 회의 배정할 여지가 많아짐
✔️ 그래서 종료 시간 기준 정렬이 핵심임

---

🧾 예제 3. 동전 0 (백준 11047)

N개의 동전 종류로 K원을 만들 때, 최소 동전 개수 구하기

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
coins.sort(reverse=True)

count = 0
for coin in coins:
    count += K // coin
    K %= coin

print(count)

✔️ 큰 단위부터 먼저 써야 최소 개수
✔️ 동전이 정렬돼 있다는 보장 없으니까 sort(reverse=True) 꼭 해줘야 함

---

🔚 마무리 요약

• 그리디는 생각보다 간단하지만,
  조건 안 맞으면 틀린 결과 나올 수 있음
• 그래서 항상 “이 선택이 전체 정답에도 유효한가?” 체크 필요
• 조건 만족하면 그리디는 진짜 빠르고 깔끔하게 풀림

그리고 실전 코테에서는
DP? 그리디? 이분탐색? 판단하는 능력이 진짜 실력임.