Post

크래프톤 정글 주제별 탐구 -그리디 알고리즘-

정의

그리디 알고리즘(Greedy Algorithm)은 현재 가장 최선의 답들만을 선택하여 최적의 해 또는 그의 근삿값을 찾아내는 방식이다.

특징

그리디의 경우, 항상 현재 보았을 때 최적의 해를 구하므로, 특정 문제들에서는 당연하게도 최선의 해가 나오지 않는 경우가 있다. 외판원 문제나 배낭(Knapsack)문제의 경우가 이에 해당한다.

이를 피하기 위해서, 그리디 알고리즘은 부분의 최적 해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다.

단점

최적의 해가 반드시 보장되지 않는다는 점과, 최악의 경우 Brute Force와 동일한 해결책이 발생할 수 있다.

알고리즘 문제

This post is licensed under CC BY 4.0 by the author.