탐욕 알고리즘(Greedy)

탐욕 알고리즘 (Greedy)

• 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황을 선택해서 답을 찾는것

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

• 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다
• 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립해야한다

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않아야한다
2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성해야한다