Greedy

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근시적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택 해 나가는 방식으로 진행하여 최종적인 해에 도달한다.

Greedy알고리즘이란 매 순간 최선의 선택을 하는 알고리즘으로 지역적으로 최선의 선택이 전역적으로도 최적의 해를 도출할 때 사용한다

Greedy의 조건

• Greedy Choice Property : 각 선택은 독립적이어야 한다. 즉, 앞의 선택이 이후의 선택에 영향을 주지 않는다
• Obtimal Substructure : 매 순간의 최적해가 전체 문제의 최적해여야 한다
  • Local optimal choice -> Global optimal solution

위의 두 조건을 만족하는 문제의 경우 Greedy알고리즘을 사용하여 문제를 해결하는 것이 유리하다

Greedy의 설계

1. Select : 한 가지 경우의 수를 선택
2. Feasibility check : 선택한 경우의 수가 최적해인지 검사
3. Solution check : 원래의 문제가 해결되었는지 검사

Greedy의 장단점

• 장점 : 구현하기 쉽고 빠르게 동작한다
• 단점 : 최적의 답이 보장되지 않는다

Greedy의 종류

• 최소 신장트리
  • Prim
  • Kruskal
• Dijkstra Algorithm : 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘
• Job Scquencing : 제한시간 안에 최대의 이익을 내도록 주어진 일의 순서를 짜는 알고리즘
• 거스름 돈 문제 : 동전개수를 최소로 하여 돈을 거슬러 줌