활동 선택 문제(Activity Selection Problem)는 시작 시간과 종료 시간이 주어진 여러 활동 중에서, 동시에 단 하나의 활동만 수행할 수 있는 사람이 선택할 수 있는 활동들을 찾는 고전적인 알고리즘 문제입니다.
이 문제에서는 다음에 수행할 활동을 선택하기 위해 그리디 알고리즘이 활용됩니다. 먼저 그리디 알고리즘이 무엇인지 살펴보겠습니다.
그리디 알고리즘이란?
그리디 알고리즘(Greedy Algorithm)은 문제를 단계별로 나누어 각 단계마다 해답을 찾아가는 방식의 알고리즘입니다. 다음 단계를 선택할 때, 알고리즘은 나머지 선택지보다 당장 가장 유망해 보이는, 즉 최적의 해답에 빠르게 도달할 수 있는 선택지를 고릅니다. 그리디 알고리즘은 매 중간 단계에서 최적화된 선택을 반복함으로써 전체 문제의 최적해에 도달하려 하기 때문에 최적화 문제를 해결하는 데 널리 사용됩니다.
다만 그리디 알고리즘이 항상 좋은 해결책이 되는 것은 아니며, 적용할 수 없는 문제도 존재합니다. 대표적인 예로 0-1 배낭 문제(0-1 Knapsack)는 그리디 알고리즘으로 최적해를 구할 수 없습니다.
대표적인 그리디 알고리즘
표준적으로 널리 알려진 그리디 알고리즘의 예는 다음과 같습니다.
1) 데이크스트라(Dijkstra) 최단 경로 알고리즘
2) 최소 신장 트리(MST) — 프림(Prim), 크루스칼(Kruskal)
3) 허프만 코딩(Huffman Coding)
활동 선택 문제의 접근 방법
활동 선택 문제에서는 시작 시간과 종료 시간을 가진 n개의 활동이 주어집니다. 이때 한 사람이 임의의 시점에 오직 하나의 활동만 수행할 수 있다는 조건 하에서, 수행할 수 있는 활동의 최대 개수를 선택해야 합니다.
핵심 아이디어는 간단합니다. 가장 먼저 끝나는 활동부터 선택하면 남은 시간이 최대한 많이 확보되어, 이후에 더 많은 활동을 선택할 여지가 생깁니다. 따라서 활동들을 종료 시간 기준으로 정렬한 뒤, 앞서 선택한 활동의 종료 시간 이후에 시작하는 활동을 차례대로 선택하면 됩니다.
예를 들어, 종료 시간을 기준으로 정렬된 3개의 활동이 있다고 가정해 보겠습니다.
Start = [1, 5, 12]
End = [10, 13, 23]
이 경우 해당 사람이 수행할 수 있는 활동은 최대 2개이며, 실제로 선택 가능한 활동은 인덱스 [0, 2]입니다. 첫 번째 활동(1~10)이 끝난 후 세 번째 활동(12~23)을 수행할 수 있기 때문입니다. 반면 두 번째 활동(5~13)은 첫 번째 활동과 시간이 겹치므로 함께 수행할 수 없습니다.
C 언어 구현 예제
#include<stdio.h>
int main(){
int start[] = {1 , 5 , 12};
int finish[] = {10, 13, 23};
int activities = sizeof(start)/sizeof(start[0]);
int i, j;
printf ("Following activities are selected \t");
i = 0;
printf("%d\t", i);
for (j = 1; j < activities; j++){
if (start[j] >= finish[i]){
printf ("%d ", j);
i = j;
}
}
return 0;
}
코드 설명
위 코드는 다음과 같은 순서로 동작합니다.
1. 배열 start와 finish에 각 활동의 시작 시간과 종료 시간을 저장합니다.
2. sizeof 연산자를 이용해 전체 활동의 개수를 계산합니다.
3. 항상 첫 번째 활동(인덱스 0)을 선택하는 것에서 시작합니다.
4. 이후 활동의 시작 시간이 직전에 선택한 활동의 종료 시간보다 크거나 같으면 해당 활동을 선택하고, 비교 기준이 되는 활동을 갱신합니다.
실행 결과
Following activities are selected 0 2
실행 결과를 해석하면, 0번 활동(시작 1, 종료 10)과 2번 활동(시작 12, 종료 23)이 선택되었음을 의미합니다. 이처럼 그리디 알고리즘을 활용하면 서로 겹치지 않는 최대 개수의 활동을 효율적으로 찾을 수 있습니다.