[자바스크립트] 그리디 (Greedy) 알고리즘

그리디(Greedy) 알고리즘 지금 순간에 가장 최적의 해를 선택하는 알고리즘 다음과 같이 위에서 아래로 이동하면서 거쳐가는 노드의 합이 가장 큰길을 찾고자 한다면 그리디 알고리즘은 아래와 같이 찾아냅니다. 노드 5에서 봤을 때는 다음으로 가장 높은 수가 100이므로 100을 선택하고, 100에서는 30을 선택합니다. 하지만 실제로 가장 높은 노드의 합은 5에서 10을 거쳐 500으로 가는 길입니다. 이렇듯 그리디 알고리즘은 항상 최적의 해를 보장해주지는 못합니다. 그리디 알고리즘은 이럴 때 좋습니다 근사 알고리즘 위에서 봤다시피 항상 최적의 해를 보장해주지는 못하지만, 어느 정도 최적에 근사한 답을 알려줍니다. 그래서 "적당히 괜찮은 해답"을 얻기 위해서는 최적의 알고리즘입니다. 또한 뒤의 경우를 더 ..

→2021.08.05