Greedy
탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근시적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택 해 나가는 방식으로 진행하여 최종적인 해에 도달한다.
Greedy알고리즘이란 매 순간 최선의 선택을 하는 알고리즘으로 지역적으로 최선의 선택이 전역적으로도 최적의 해를 도출할 때 사용한다
Greedy의 조건
- Greedy Choice Property : 각 선택은 독립적이어야 한다. 즉, 앞의 선택이 이후의 선택에 영향을 주지 않는다
- Obtimal Substructure : 매 순간의 최적해가 전체 문제의 최적해여야 한다
- Local optimal choice -> Global optimal solution
위의 두 조건을 만족하는 문제의 경우 Greedy알고리즘을 사용하여 문제를 해결하는 것이 유리하다
Greedy의 설계
- Select : 한 가지 경우의 수를 선택
- Feasibility check : 선택한 경우의 수가 최적해인지 검사
- Solution check : 원래의 문제가 해결되었는지 검사
Greedy의 장단점
- 장점 : 구현하기 쉽고 빠르게 동작한다
- 단점 : 최적의 답이 보장되지 않는다
Greedy의 종류
- 최소 신장트리
- Dijkstra Algorithm : 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘
- Job Scquencing : 제한시간 안에 최대의 이익을 내도록 주어진 일의 순서를 짜는 알고리즘
- 거스름 돈 문제 : 동전개수를 최소로 하여 돈을 거슬러 줌