# Greedy Algorithm

- Greedy Algorithm은 local optimal solution 을 찾는 것이 결국에는 global solution을 찾는 경우 Greedy algorithm 이 적절하다. 반대로, local optimal solution 이 global solution 을 보장하지 않는 경우에는 Greedy algorithm 이 적절하지 않다.
- Greedy algorithm 을 이해하기 좋은 문제는 Fractional Knapsack Problem 임.
- Fractional Knapsack Problem 을 이해하기 위해서는 0-1 knapsack problem 을 이해해야함.
- 0-1 knapsack problem 은 아이템을 쪼개는 것이 불가능함. 쪼개는 것이 가능하면 Fractional 임.
- 전체 용량이 $W$ 인 knapsack 이 있고, $n$개의 item 이 있다고 하자. 그리고 각각의 아이템은 무게 $w_i$ 와 가격 $p_i$ 를 갖는다. 이런 경우 가장 많은 가격을 갖도록 얻을 수 있는 방법은?
- Fractional 문제인 경우 Greedy 를 사용해도 됨
- 0-1 knapsack 문제의 경우 DP 를 사용해야함.
- :face_with_monocle: