[Algorithms] Greedy Approach

어떠한 선택을 연속적으로 하는데,
그 순간순간 가장 좋아보이는 것을 선택하여 솔루션을 만들어 내는 접근법을 Greedy Approach라고 한다.

각각의 선택은 locally optimal하지만 global optimal하지는 않을 수도 있다.
Greedy approach의 장점은 쉽게 알고리즘을 풀어나갈 수 있다는 것이지만,
단점은 항상 optimal 하다는 것을 보장하지 못한다는 것이다.

따라서, 수학적인 증명을 통해 optimal 여부를 판단해야 한다.

일반적으로 이 접근법은 세가지 절차로 나눌 수 있다.
1. Selection Procedure
 어떠한 기준(Greedy Criteria)을 가지고 선택한다.
2. Feasibility Check
 새롭게 선택한 것이 해를 만드는데 있어서 적합한지 판단한다.
3. Solution Check
 만들어진 인스턴스의 set이 해를 만들어내는지 판단한다.


이 알고리즘 접근법을 사용하는 대표적인 예로 Minimum spanning tree 구하는 알고리즘(Prim, Kruskal), 허프만 코드(Huffman Code) 생성 알고리즘 등등이 있다.