그리디 알고리즘
-
[알고리즘] 그리디 알고리즘(Greedy Algorithms)STUDY/Algorithm 2021. 4. 1. 11:08
그리디 알고리즘(Greedy Algorithms) 그리디 알고리즘은 문제 해결과정에서 순간순간마다 최적이라고 생각되는 해를 선택하여, 최종 해답에 도달하는 문제 해결 방식이다. 위의 그림은, 선택을 해야하는 순간에 가장 최선이라고 생각되는 해를 선택하는 동작방식을 보여준다. 최대 값을 구할때, 1과 9 중 하나를 골라야할때, 그 뒤의 값들은 전혀 고려하지 않고, 당장의 1과 9만 두고 어떤 것을 선택할지 고른다. 1과 9 중에는 당연히 9가 크기 때문에 9를 고르고, 3과 12 중에는 12를 고르게 된다. 이런 식으로 구한 최대 값은 12이다. 하지만 그림을 보면 알 수 있듯 이 이진 트리에서 최대 값은 99이다. 이렇듯 그리디 알고리즘과 같이 순간순간 최선의 결정을 선택하는 것이 항상 문제의 최선의 해..