Greedy

1. Greedy Algorithm 이란?

Greedy Algorithm(탐욕 알고리즘) 은 "현재 상황에서 가장 좋아보이는(최적의) 선택을 반복해서 전체 최적 해에 도달하려는 전략" 임.

• 매 단계에서 로컬 최적(local optimum) 을 선택하지만, 이 선택이 전체적으로도 글로벌 최적(global optimum) 이 될 수 있어야 함.

• 보통 그리디는 DP 보다 빠르고 간단하지만, 항상 정답을 보장하지는 않음

---

2. Greedy 가 잘 작동하는 조건

1. 탐욕적 선택 속성(Greedy Choice Property)

• 앞의 선택이 이후의 선택에 영향을 주지 않아야 함

• 즉, "지금 이 순간 가장 좋은 선택을 하면, 전첵적으로 최적이다" 는 것을 증명할 수 있어야 함.

2. 최적 부분 구조(Optimal Substructure)

• DP 와 동일. 문제의 전체 최적 해가 하위 문제들의 최적 해로 구성되어야 함.

이 두 조건을 만족하는 문제만 그리디로 풀 수 있음

만족하지 않으면 DP 나 완전탐색(Brute Force) 을 써야함.

---

3. 대표적인 Greedy 알고리즘 예시

문제	핵심 아이디어
동전 거스름돈	큰 단위 동전부터 최대한 사용
회의실 배정	종료 시간이 가장 빠른 회의부터 선택
배낭 문제(분할 허용 시)	무게 대비 가치가 높은 물건부터 선택
최소 스패닝 트리	Kruskal, Prim 알고리즘
Huffman Coding	빈도 낮은 문자부터 병합
활동 선택 문제	활동 종료 시간이 빠른 순으로 선택

---

4. 예제 : 동전 거스름돈 문제

문제

• 거스름돈을 줄 떄 동전 개수가 최소가 되도록 주는 방법을 구하시오.

• 동전 단위 : 500원, 100원, 50원, 10원

• 예 : 1260원을 거슬러 줘야 한다면?

풀이

• 가장 큰 단위부터 최대한 사용 ⇒ 그게 현재 최선의 선택

• 500원부터 나누어가며 몫과 나머지를 구함.

int[] coins = {500, 100, 50, 10};
int n = 1260;
int count = 0;

for(int coin : coins) {
    count += n / coin; // 사용할 수 있는 최대 개수
    n %= coin; // 남은 금액
}
System.out.println(count); // result : 6

• 500 * 2 + 100 * 2 + 50 * 1 + 10 * 1 = 1260 ⇒ 총 6개

위 문제는 그리디가 항상 최적인 이유: 동전 단위가 "배수 관계" 로 되어 있기 때문.

---

5. Greedy vs DP

항목	그리디	DP
전략	현재 최적 선택	모든 경우 고려
시간복잡도	보통 더 빠름 (O(N log N))	보통 느림 (O(N²), O(NM) 등)
조건	탐욕적 선택 속성, 최적 부분 구조	중복 부분 문제, 최적 부분 구조
구현	간단한 편	복잡하고 메모리도 필요
정답 보장	조건 만족 시만 보장	항상 보장됨

---

6. 실전에서 Greedy 적용 팁

1. 정렬이 거의 필수 - 어떤 기준으로 정렬 후 순차적으로 처리

2. "현재 순간 최적" 이 전체 최적이 되는지 직관 + 수학적으로 검증

3. 그리디로 풀렸다고 확신이 안 되면, 반례 테스트 해보자

4. 그리디가 안 먹힌다 싶으면 DP/완전탐색으로 방향 전환