그리디(탐욕) 알고리즘

그리디 (탐욕) 알고리즘은 현재 상황에서 최적의 해를 찾는 알고리즘이다. 알고리즘 구현은 단순하지만 단점도 존재한다.

A 위치에서 시작해서 해당 그래프의 최고점을 찾는다고 했을 때, A에서 최적의 선택은 C 방향으로 올라가는 것이다. 그러나 그래프 전체를 봤을 때는 B가 최고점이다. 이렇듯 그리디 알고리즘은 항상 최적의 결과를 찾아내지는 못하지만 최적에 근사한 결과를 찾아낼 수 있다.

 

과목 선택 문제에서 그리디 알고리즘을 사용할 수 있다. 예를 들어 한 강의실에서 최대한 많은 수업을 진행할 수 있는 경우를 찾아야 한다고 하자. 수업 시작 시간과 종료 시간이 주어줬을 때 다음과 같은 순서로 문제를 해결할 수 있다.

 

1. 수업이 가장 빨리 끝나는 과목을 찾는다.
2. 해당 과목이 끝난 후에 다음으로 가장 빨리 끝나는 과목을 찾는다.

위 방법을 반복했을 때 최적의 값을 찾을 수 있다.