탐욕 알고리즘 (Greedy Algorithm)

탐욕 알고리즘이란?

말그대로 Greedy하게, 탐욕스럽게 그 때 그 때의 최적의 상황을 쫓아 문제를 해결하는 방법이다.

여러 경우 중 하나를 결정해야할 때 그 순간에 최적이라고 생각되는 것을 선택해나가며 최종 해답에 도달한다.

 

알고리즘을 적용하기 위한 전제 조건

1) 탐욕적 선택 속성 (Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.

2) 최적 부분 구조 (Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

문제 해결 절차

1) 선택 절차 (Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.

2) 적절성 검사 (Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.

3) 해답 검사 (Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

 

 

참고자료

하나몬, 2021.08.24, [알고리즘] 탐욕 알고리즘(Greedy Algorithm)

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬