Greedy(탐욕 알고리즘)

1. Greedy(탐욕 알고리즘)

"지금 당장 최적의 선택이 최종적으로도 최적일 것이다."

 

2. DP하고 어떻게 다르죠?

구분	Greedy	DP
핵심원리	지금 당장 최적의 선택이 최종적으로도 최적일 것이다.	작은 문제의 최적 해를 저장하고, 이를 조합해 큰 문제의 최적 해를 구한다.
선택기준	각 단계에서 가장 좋은 현재 선택 (미래를 고려하지 않음).	작은 문제의 최적 해를 이용 (모든 가능한 경우를 간접적으로 고려).
부분 문제	한 번의 선택이 다음 단계에 영향을 주지만, 중복되는 부분 문제는 없음.	중복되는 부분 문제가 발생함.
최적의 해 보장	특정 구조의 문제에서만 보장됨 (모든 최적화 문제에서 통하지 않음).	최적 부분 구조를 가진 문제라면 항상 최적 해를 보장함.
예시 상황	거스름돈 최소 개수 (화폐 단위가 1, 5, 10, 500 등 배수 관계일 때), 프림/크루스칼 알고리즘.	배낭 문제, 최장 공통 부분 수열 (LCS), 설탕 배달 (정석), 피보나치 수열.

 

 

3. DP문제인지 Greedy로 풀것인지 구분하는 방법

Greedy 알고리즘은 항상 최적의 해를 보장하지 않음으로, 풀이전에 2가지 부분에 대해서 반드시 확인해야 한다. 

 

1) 탐욕적 선택 속성(Greedy Choice Property) : 지역적인 최적 해를 선택해도 결국 전역적인(Global) 최적 해를 구할 수 있어야 한다. 
=> 당장의 최선을 선택해도 최종 결과에 해가 되지 않아야 한다. 

 

2) 최적 부분 구조(Optimal Substructure) : 문제의 최적 해가 그 문제의 작은 부분 문제들의 최적 해를 포함하고 있어야 한다. (DP와 동일한 속성)