Greedy Algorithm 탐욕법
매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식
→ 현재 상황에서 지금 당장 좋은 것만을 고르는 방법
문제풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있음
항상 최적의 결과를 보장하지는 못함, but 근사값 빠르게 도출 가능
따라서 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못합니다. 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 합니다.
•
탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
•
최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
탐욕법으로 문제를 해결하는 방법은 단계적으로 구분 가능
1.
선택 절차 : 현재 상태에서의 최적의 해답을 선택
2.
적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
3.
해답 검사 : 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택 절차로 돌아가 위 과정 반복
최소비용 신장 트리 : 그래프 내의 모든 정점을 최소 비용으로 연결하는 트리
- kruskal 알고리즘 : 최소비용 신장 트리를 만드는 알고리즘 중 탐욕 알고리즘을 이용한 풀이