Contents
- Greedy algorithm
1-1. Basic structure
1. Greedy algorithm
A heuristic approach for solving optimization problems by making locally optimal choices at each step in order to find a global optimum solution.
어떤 문제에 대해 모든 가능성을 탐색한 후 solution 을 찾는 brute-force algorithm 과는 달리 greedy algorithm 은 각각의 단계에서 당장 좋은 방법만을 선택해나가며 그 중 global optimum solution 을 찾는다. 때에 따라서 greedy algorithm 은 suboptimal solution 을 주기도 하는데, 이는 최적해에 대한 빠르고 효율적인 good approximation 을 제공한다.
It is called “greedy” because it tries to find the best solution by making the best choice at each step, without considering future steps or the consequences of the current decision.
하지만 많은 경우에 greedy strategy 는 최적의 해를 찾지 못한다는 문제점이 있다. 그러므로 우리는 greedy algorithm 을 이용해 최적의 해를 찾을 수 있음이 보장된 문제에만 해당 알고리즘을 사용하며 그 정당성을 증명하는 과정을 연습해야 한다.
Greedy algorithm works for cases where minimization or maximization leads to the required solution.
Common use cases 로는 최소값이나 최댓값을 찾는 몇몇 optimization problems 가 있으며, graph 의 minimum spanning tress 를 찾는 문제를 예로 들 수 있겠다.
1-1. Basic structure
모든 greedy algorithm 은 1) empty result = 0 를 declare 하고, 2) greedy choice 가 feasible 하면 final result 에 포함시킨 후, 3) return 을 하는 구조를 가진다.
