탐욕법 - 활동 선택 문제(Activity Selection Problem)

 

우리가 흔히 알고리즘에서 사용하는 탐욕법은 현재 위치에서 가장 최적의 해를 구해가는 과정을 연속해서 진행하는 문제이다. 이러한 문제 유형 중에는 활동 선택 문제가 있는데 이는 n개의 시작점과 끝점을 주어진다. 문제를 해결하는 사람은 한번에 하나의 행동만 작업할 수 있기 때문에 이러한 행동의 합을 최대로 만드는 문제이다.

 

활동선택 문제는 활동 중에서 종료 시간을 기준으로 해당 내용들을 정렬하여 해결할 수 있다. 이에 대한 코드는 아래 위키피디아를 참고하면 된다.

 

en.wikipedia.org/wiki/Activity_selection_problem

 

활동 선택 문제를 해결하는 방법은 먼저 각 활동에 대한 종료시간을 기준으로 오름차순하고, 첫 활동에서부터 다음활동 시작시간이 전 활동의 종료시간보다 짧으면 그 활동을 선택하는 것을 이어가며 문제를 해결할 수 있다.