그리디 알고리즘

 

그리디 알고리즘

그리디 알고리즘이란 최적화 문제를 해결하는 알고리즘, 각 단계에서 지금 당장 최적의 선택을 계속해서 내려가면서 최종적으로 전체적으로 최적해를 찾아내는 방식이다.

 

예를 들어 최소 스패닝 트리, 최단 경로, 배낭 문제 등에 적용 할 수 있다.

 

다음과 같은 구조를 같습니다.

1. 해의 후보 중에 하나를 선택합니다.

2. 선택한 후보가 문제의 제약 조건에 부합하는지 확인합니다.

3. 부합한다면, 선택한 후보를 정답에 추가하고, 문제의 제약 조건을 수정합니다.

4. 제약 조건을 만족할때까지 1-3단계를 반복합니다.

 

각 단계에세 지금 당장의 최적인 선택을 하기에, 전체적인 최적해를 찾기 위해선 이러한 선택이 계속 이루어져야 합니다. 

하지만, 항상 최적의 해를 보장하지 않습니다.

 

대표적인 문제로는 동전문제가 있습니다.