7-3. 그리디: 활동 선택 문제

1. 활동 선택 문제의 이해

활동 선택 문제는 그리디 알고리즘을 적용하여 효율적으로 풀 수 있는 대표적인 문제 중 하나입니다. 여러 개의 활동(activity)이 주어지고, 각 활동은 시작 시간과 종료 시간을 갖습니다. 목표는 서로 겹치지 않으면서(non-overlapping) 최대한 많은 활동을 선택하는 것입니다. 이러한 문제는 회의 스케줄링, 자원 할당, 작업 일정 관리 등 실생활의 다양한 상황에서 발생합니다.

예를 들어, 여러 개의 강연이 있고 각 강연의 시작 시간과 종료 시간이 주어졌을 때, 겹치는 강연 없이 최대한 많은 강연을 선택하여 들을 수 있는 경우를 생각해 볼 수 있습니다.

1) 문제의 정의

활동 선택 문제는 다음과 같이 정의됩니다.

• 입력:
  • $n$개의 활동. 각 활동 $i$는 시작 시간 $s_i$와 종료 시간 $f_i$를 갖습니다.
• 출력:
  • 선택된 활동들의 최대 부분 집합 $A$, 여기서 $A$에 속한 모든 활동은 서로 겹치지 않습니다. 즉, 어떤 두 활동 $i$와 $j$ ($i \ne j$)에 대해, $s_i \ge f_j$ 또는 $s_j \ge f_i$여야 합니다.

2) 왜 그리디 알고리즘인가?

활동 선택 문제는 최적 부분 구조(optimal substructure)와 탐욕적 선택 속성(greedy choice property)을 만족하기 때문에 그리디 알고리즘을 사용하여 효율적으로 해결할 수 있습니다.

• 최적 부분 구조: 문제의 최적 해는 부분 문제의 최적 해를 포함합니다. 즉, 전체 활동 집합에 대한 최적 해를 구하기 위해, 선택된 활동들을 제외한 나머지 활동들에 대한 최적 해를 구할 수 있습니다.
• 탐욕적 선택 속성: 각 단계에서 최적의 선택(탐욕적인 선택)을 하면 전체 문제에 대한 최적 해를 구할 수 있습니다. 활동 선택 문제의 경우, 가장 먼저 종료되는 활동을 선택하는 것이 탐욕적인 선택입니다. 왜냐하면, 먼저 종료되는 활동을 선택하면, 그 활동이 끝난 후에 더 많은 활동을 선택할 수 있는 기회가 생기기 때문입니다.

2. 그리디 알고리즘 적용: 활동 정렬과 선택

활동 선택 문제를 해결하기 위한 그리디 알고리즘은 다음과 같은 단계로 구성됩니다.

1. 활동 정렬: 모든 활동을 종료 시간 기준으로 오름차순으로 정렬합니다.
2. 활동 선택: 정렬된 활동들을 순차적으로 살펴보면서, 현재 선택된 활동과 겹치지 않는 활동을 선택합니다.

1) 활동 정렬의 중요성

활동을 종료 시간 기준으로 정렬하는 것은 그리디 알고리즘의 핵심입니다. 정렬을 통해 각 단계에서 가장 먼저 종료되는 활동을 쉽게 선택할 수 있습니다. 이는 선택 가능한 활동의 범위를 최대한 넓혀 전체 활동의 수를 최대화하는 데 기여합니다.

2) 알고리즘의 동작 방식

1. 초기화: 선택된 활동 집합 $A$를 빈 집합으로 초기화합니다. 정렬된 활동 리스트에서 첫 번째 활동을 $A$에 추가합니다.
2. 반복: 정렬된 활동 리스트의 나머지 활동들을 순회합니다.
   • 현재 활동의 시작 시간이 $A$에 있는 마지막 활동의 종료 시간보다 늦거나 같다면, 현재 활동을 $A$에 추가합니다.
   • 그렇지 않다면, 현재 활동을 무시합니다.
3. 출력: $A$를 반환합니다.

3) pseudo-code

function activitySelection(activities):
    // 활동을 종료 시간 기준으로 정렬
    sort activities by finish time

    selectedActivities = [activities[0]] // 첫 번째 활동을 선택

    for i from 1 to activities.length - 1:
        if activities[i].start_time >= selectedActivities[-1].finish_time:
            selectedActivities.append(activities[i])

    return selectedActivities

3. 예제

다음은 활동 선택 문제의 예시입니다.

1) 활동 정렬

활동들을 종료 시간 기준으로 정렬하면 다음과 같습니다.

위의 정렬된 결과는 올바르지 않습니다. 활동 C와 F는 종료 시간이 동일하지만, 시작 시간이 다르기 때문에, 문제의 정의에 따라 정렬에 포함되어야 합니다. 또한, 활동 B, D, F는 시작 시간이 같지만 종료 시간이 다르기 때문에, 종료 시간을 기준으로 정렬되어야 합니다. 따라서, 위 표는 잘못된 예시입니다. 올바른 정렬은 다음과 같습니다.

2) 그리디 알고리즘 적용

1. A 선택: 첫 번째 활동 A를 선택합니다. selectedActivities = [A]
2. B 선택: 활동 B의 시작 시간(3)은 A의 종료 시간(2)보다 늦으므로 B를 선택합니다. selectedActivities = [A, B]
3. C 선택: 활동 C의 시작 시간(0)은 B의 종료 시간(4)보다 빠르므로 C를 선택하지 않습니다.
4. D 선택: 활동 D의 시작 시간(5)은 B의 종료 시간(4)보다 늦으므로 D를 선택합니다. selectedActivities = [A, B, D]
5. E 선택: 활동 E의 시작 시간(8)은 D의 종료 시간(7)보다 늦으므로 E를 선택합니다. selectedActivities = [A, B, D, E]
6. F 선택: 활동 F의 시작 시간(5)은 E의 종료 시간(9)보다 빠르므로 F를 선택하지 않습니다.

따라서 선택된 활동은 A, B, D, E이며, 총 4개의 활동을 선택할 수 있습니다.

4. 구현 및 최적화 고려 사항

활동 선택 문제는 그리디 알고리즘을 사용하여 간단하게 구현할 수 있습니다. 하지만, 효율적인 구현을 위해 몇 가지 고려 사항이 있습니다.

1) 자료구조 선택

활동 정보를 저장하는 데 적합한 자료구조를 선택해야 합니다. 일반적으로, 활동의 시작 시간과 종료 시간을 묶어 저장하는 class 또는 struct를 사용하는 것이 좋습니다. 활동들을 종료 시간 기준으로 정렬하기 위해, 정렬 기능을 지원하는 list 또는 array와 같은 자료구조를 사용할 수 있습니다.

2) 정렬 알고리즘 선택

활동 정렬 단계는 알고리즘의 성능에 큰 영향을 미칩니다. O(n log n)의 시간 복잡도를 갖는 정렬 알고리즘(예: 병합 정렬, 퀵 정렬)을 사용하는 것이 일반적입니다.

3) 시간 복잡도 분석

• 정렬: O(n log n)
• 활동 선택: O(n) (정렬된 활동 리스트를 한 번 순회)
• 전체: O(n log n) (정렬 단계가 지배적)

5. 결론

활동 선택 문제는 그리디 알고리즘의 좋은 예시이며, 실제 문제 해결에 널리 활용됩니다. 종료 시간 기준으로 활동을 정렬하고, 겹치지 않는 활동들을 선택하는 간단한 전략을 통해 최적의 해를 구할 수 있습니다.

이 문제의 핵심은 활동을 종료 시간 기준으로 정렬하는 것입니다. 이를 통해 각 단계에서 가장 먼저 종료되는 활동을 선택하고, 더 많은 활동을 선택할 수 있는 기회를 확보할 수 있습니다.

활동 선택 문제의 원리를 이해하고, 그리디 알고리즘을 효과적으로 적용하면, 다양한 스케줄링 및 자원 할당 문제를 해결하는 데 도움이 될 것입니다.