그리디 알고리즘(탐욕법)

1. 그리디 알고리즘

  - 최적 해를 구하는 데 사용되는 근시안적인 방법

  - 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식

  - 각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.

  - 한번 선택된 것은 번복하지 않는다.

 

---

 

2. 그리디 vs 다이나믹 프로그래밍

분류	그리디 알고리즘(Greedy Algorithm)	동적 계획법(DP: Dynamic Programming)
설명	각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방식	작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결하는 방식
성립 조건	1. 탐욕 선택 속성(Greedy Choice Property) 2. 최적 부분 구조(Optimal Substructure)	1. 중복 부분 문제 (Overlapping Subproblems) 2. 최적 부분 구조 (Optimal Substructure)
중복 부분 문제	중복 부분 문제를 해결하지 않습니다.	중복 부분 문제를 해결할 수 있습니다.
상황	- 각 단계의 상황에서 최적을 선택하여 최적의 경로를 구합니다. - 최적이 아닌 경우가 될수 있거나 혹은 풀리지 않는 문제가 될수 있습니다.	- 모든 상황을 계산하여 최적의 경로를 구할 수 있습니다 - 모든 상황을 계산하기에 시간이 오래 걸립니다.

 

---

 

3. 탐욕 알고리즘의 필수 요소

  - 탐욕 적 선택 속성 : 탐욕 전 선택은 최적해로 갈 수 있음을 보여라.

  - 최적 부분 구조 : 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.