오늘은 알고리즘 중 하나인 Greedy에 관하여 알아보도록 하겠다.

Greedy

Greedy 탐욕법 알고리즘은 결과까지는 생각하지 않고 매 순간 최선이라고 생각되는 것을 선택해 결과까지 도달하는 알고리즘이다. 설명과 같이 매 순간 최 선인 선택을 하고 그 이후의 선택은 이후에 판단하기 때문에 언제나 옳은 알고리즘은 아닐 수 있다. 그렇기 때문에, 현상황에서 선택하는 최선의 수를 선택 한다면 결과도 최선이 되는 경우에 사용하여야 알맞다. 보통은 활동 선택 문제, 거스름돈 문제, 최소 신장 트리, 다익스트라 알고리즘에 활용이 가능하며, 살펴보다면 결국 매순간 최적의 선택을하고 그 선택들이 다음 선택과 전혀 무관하더라도 최적의 경우를 찾을 수 있는 문제에 사용이 가능한 것을 알 수 있다.

탐욕범을 위한 문제 탐욕법의 정의이고, 나머지는 문제를 풀어보며 어떻게 접근하여야 할지 생각해 봐야하겠다. 추가적인 문제를 다룰 경우 추가 포스팅 예정임.