그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘은 탐욕 알고리즘이라고도 불린다. 그리디 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나이다.

 

여러 경우 중 하나를 결정해야 할 때마다 그 순간의 최적이라고 생각되는 것을 선택해 나가는 알고리즘이다. 

 

하지만 그리디 알고리즘을 적용할 수 있는 예는 많지 않다. 코딩이 쉽고, 구현이 쉬운건 사실이지만, 그리디 알고리즘으로 구한게 항상 최적을 보장하는 경우는 거의 없기 때문이다. 만약에 사탕을 당장 받으면 1개만 받지만, 1분을 기다리면 2개를 받을 수 있다고 하자. 이런 경우 그리디 알고리즘을 사용하면 사탕을 1개 받는 것을 선택한다. 그래서 보통 '근사치 추정'을 위해 그리디 알고리즘을 사용한다.

 

적용 가능한 예

Prim Algorithm, Kruskal Algorithm, Dijkstra Algorith, Task Scheduling Problem, 거스름돈 나누기 등