건빵의 블로그

어떠한 선택을 연속적으로 하는데, 그 순간순간 가장 좋아보이는 것을 선택하여 솔루션을 만들어 내는 접근법을 Greedy Approach라고 한다. 각각의 선택은 locally optimal하지만 global optimal하지는 않을 수도 있다. Greedy approach의 장점은 쉽게 알고리즘을 풀어나갈 수 있다는 것이지만, 단점은 항상 optimal 하다는 것을 보장하지 못한다는 것이다. 따라서, 수학적인 증명을 통해 optimal 여부를 판단해야 한다. 일반적으로 이 접근법은 세가지 절차로 나눌 수 있다. 1. Selection Procedure 어떠한 기준(Greedy Criteria)을 가지고 선택한다. 2. Feasibility Check 새롭게 선택한 것이 해를 만드는데 있어서 적합한지 판단..