시작 시간과 종료 시간이 주어진 n개의 서로 다른 활동이 있을 때, 한 사람이 수행할 수 있는 최대 개수의 활동을 선택하는 것이 활동 선택 문제(Activity Selection Problem)입니다. 이 문제는 그리디(Greedy) 접근법으로 효율적으로 해결할 수 있습니다.
핵심 아이디어는 간단합니다. 남은 활동 중 종료 시간이 가장 빠른 활동을 우선 선택하고, 그다음에는 마지막으로 선택한 활동의 종료 시간보다 늦게 시작하거나 같은 시간에 시작하는 활동만을 차례로 고르는 것입니다. 종료가 빠른 활동을 먼저 배정할수록 이후에 선택할 수 있는 활동의 여유가 많아지기 때문에, 이 전략은 항상 최적해를 보장합니다.
- 활동 목록이 정렬되어 있지 않은 경우 시간 복잡도는 O(n log n)입니다.
- 이미 정렬된 목록이 주어진 경우 시간 복잡도는 O(n)입니다.
입력과 출력
입력:
시작 시간과 종료 시간을 가진 활동 목록
{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}
출력:
선택된 활동 목록:
Activity: 0 , Start: 1 End: 2
Activity: 1 , Start: 3 End: 4
Activity: 3 , Start: 5 End: 7
Activity: 5 , Start: 8 End: 9
알고리즘
maxActivity(act, size)
입력: 활동 목록과 목록에 포함된 원소의 개수
출력: 선택된 순서대로 나열된 활동 목록
Begin
주어진 활동 목록을 먼저 정렬한다
i := 0 으로 설정
i번째 활동을 출력한다 // 첫 번째 활동
for j := 1 to n-1 do
if act[j]의 시작 시간 >= act[i]의 종료 시간 then
j번째 활동을 출력한다
i := j
done
End
C++ 예제 코드
#include<iostream>
#include<algorithm>
using namespace std;
struct Activitiy {
int start, end;
};
// 종료 시간을 기준으로 오름차순 정렬하기 위한 비교 함수
bool comp(Activitiy act1, Activitiy act2) {
return (act1.end < act2.end);
}
void maxActivity(Activitiy act[], int n) {
sort(act, act+n, comp); // 비교 함수를 사용해 활동을 정렬
cout << "Selected Activities are: " << endl;
int i = 0; // 첫 번째 활동(인덱스 0)을 선택
cout << "Activity: " << i << " , Start: " << act[i].start << " End: " << act[i].end << endl;
for (int j = 1; j < n; j++) { // 나머지 모든 활동 검사
if (act[j].start >= act[i].end) { // 시작 시간이 이전 활동의 종료 시간 이상이면 선택
cout << "Activity: " << j << " , Start: " << act[j].start << " End: " << act[j].end << endl;
i = j;
}
}
}
int main() {
Activitiy actArr[] = {{5,9},{1,2},{3,4},{0,6},{5,7},{8,9}};
int n = 6;
maxActivity(actArr,n);
return 0;
}
실행 결과
Selected Activities are:
Activity: 0 , Start: 1 End: 2
Activity: 1 , Start: 3 End: 4
Activity: 3 , Start: 5 End: 7
Activity: 5 , Start: 8 End: 9
위 실행 결과에서 볼 수 있듯이, 종료 시간 기준으로 정렬한 뒤 겹치지 않는 활동을 순서대로 선택하면 총 4개의 활동을 충돌 없이 수행할 수 있습니다. 이처럼 활동 선택 문제는 회의실 예약, 강의 편성 등 실생활의 일정 관리 문제에 널리 응용되는 대표적인 그리디 알고리즘 예제입니다.