C++로 풀어보는 활동 선택 문제 (그리디 알고리즘 1)

시작 시간과 종료 시간이 주어진 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++ 구현 예제

다음은 위 알고리즘을 C++로 구현한 코드입니다. 비교 함수를 사용해 활동을 종료 시간 기준 오름차순으로 정렬한 뒤, 앞서 선택한 활동과 겹치지 않는 활동을 차례로 골라냅니다.

#include<iostream>
#include<algorithm>
using namespace std;
struct Activity {
    int start, end;
};
// 종료 시간 기준 오름차순 정렬을 위한 비교 함수
bool comp(Activity a1, Activity a2) {
    return (a1.end < a2.end);
}
void maxActivity(Activity act[], int n) {
    sort(act, act+n, comp); // 비교 함수를 사용해 활동 정렬
    cout << "Selected Activities are: " << endl;
    int i = 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() {
    Activity 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

예제 동작 과정 살펴보기

입력된 활동을 종료 시간 기준으로 정렬하면 (1,2) → (3,4) → (0,6) → (5,7) → (5,9) → (8,9) 순서가 됩니다. 먼저 첫 번째 활동 (1,2)을 선택하고, (3,4)는 시작 시간 3이 직전 활동의 종료 시간 2보다 크므로 선택됩니다. 반면 (0,6)은 시작 시간이 0이라 제외되며, (5,7)은 종료 시간 4 이후에 시작하므로 선택됩니다. (5,9)는 (5,7)과 시간이 겹쳐 제외되고, 마지막 (8,9)은 종료 시간 7 이후에 시작하므로 선택됩니다. 그 결과 서로 겹치지 않는 총 4개의 활동이 선택됩니다.