Greedy Algorithm

문제 해결 단계:
1. 선택 절차(Selection Procedure): 현재 상태에서 최적의 해답을 선택합니다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.
탐욕 알고리즘: 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optinal solution)에 도달하는 문제 해결 방식. 항상 최적의 결과를 보장하지는 못한다. 탐욕 알고리즘을 적용하려면 다음의 2가지 조건이 성립하여야 한다.
1. 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
2. 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 근사한 값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.