그리디 알고리즘

욕심쟁이 알고리즘

매 선택에서 지금 이 순간 최적인 답을 선택하여 적합한 결과를 도출하자 라는 모토를 가지는 알고리즘 설계 기법

 

 

 

예를 들어,
5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다.
이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다.

가능한 120가지의 조합을 모두 살펴봐서 그 중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다.

 

그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다.

 

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것.

매 순간 최적을 따라가서 1-1-1-100 이라는 순서로 길을 갔다면, 종합적으로는 1-1-10-10의 길로 가는 것이 더 짧은 길이 될 수 있다.

 

 다익스트라 알고리즘이나
MST(minimum spanning Tree)알고리즘을 구현할 때 사용할 수 있다.