그리디 알고리즘

그리디 알고리즘(탐욕법, Greedy Algorithm)

최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘

이 때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 ‘근사한 값’을 목표로 한다.

문제 예시

1. 노드에서 가장 합이 높은 방법을 선택하는 방법은 ?

   • 아래의 경우에서는 기준 없이 선택을 하는 경우
     

   • 아래의 경우에서는 그리디 알고리즘과 같은 형태로 노드를 선택하는 방식

     각각 상황에서 최적이라고 생각하는 방법을 선택한다. (상황에서 가장 높은 수)

   
   

그리디 알고리즘 주요 속성

그리디 알고리즘은 문제를 풀 때 두 가지 조건이 성립해야 그리디 알고리즘을 적용할 수 있다.

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

   각 단계에서 최적의 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말한다.

   즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것이다.

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

   전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우를 말한다.

   즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적 해를 구하는 것을 의미한다.

그리디 알고리즘 단계

그리디 알고리즘의 단계는 매 단계마다 최적이라고 생각되는 선택을 하면서 최종적으로 전체적으로 최적인 해답을 찾아내는 과정을 의미한다.

1. 문제의 최적해 구조를 결정한다.
2. 문제의 구조에 맞게 선택 절차를 정의한다.
3. 선택 절차에 따라 선택을 수행한다.
4. 선택된 해가 문제의 조건을 만족하는 지 적절성을 검사한다.
5. 조건을 만족하지 않으면 해당 해를 제외한다.
6. 모든 선택이 완료되면 해답을 검사한다.
7. 조건을 만족하지 않으면 해답으로 인정되지 않는다.

그리디 알고리즘 vs 동적 계획법

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