이 글에서는 활동 선택 문제(Activity Selection Problem)를 파이썬으로 해결하는 방법을 예제 코드와 함께 단계별로 살펴보겠습니다.
문제 정의
각 활동마다 시작 시간과 종료 시간이 주어진 n개의 활동이 있습니다. 한 사람은 동시에 두 개 이상의 활동을 수행할 수 없다는 조건 하에서, 이 사람이 수행할 수 있는 최대 개수의 활동을 선택하는 것이 목표입니다.
사용되는 변수
- N — 전체 활동의 개수
- S — 모든 활동의 시작 시간을 저장한 배열
- F — 모든 활동의 종료 시간을 저장한 배열
해결 접근 방식: 그리디(Greedy) 알고리즘
활동 선택 문제는 그리디 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 전략은 다음과 같습니다.
- 활동을 종료 시간 기준으로 오름차순 정렬합니다.
- 가장 먼저 끝나는 첫 번째 활동은 항상 선택합니다.
- 나머지 활동 중에서 직전에 선택한 활동의 종료 시간보다 시작 시간이 같거나 늦은 활동을 차례로 선택합니다.
종료가 빠른 활동을 우선 선택하면 다음 활동을 위해 가용 시간이 최대한 확보되므로, 전체적으로 더 많은 활동을 수행할 수 있습니다.
구현 예제
# 한 사람이 수행할 수 있는 최대 활동 수 구하기 (그리디 방식)
def Activities(s, f):
n = len(f)
print("선택된 활동:", end=" ")
# 첫 번째 활동은 항상 선택됨
i = 0
print(i, end=" ")
# 나머지 활동 검사
for j in range(1, n):
# 시작 시간이 이전 활동의 종료 시간보다 크거나 같으면 선택
if s[j] >= f[i]:
print(j, end=" ")
i = j
# 메인 실행부
s = [1, 2, 0, 3, 2, 4]
f = [2, 5, 4, 6, 8, 8]
Activities(s, f)
실행 결과
선택된 활동: 0 1
코드 설명
함수 내에서 선언된 모든 변수는 지역 범위(local scope)에 속하며, 함수 실행이 끝나면 소멸합니다. 알고리즘의 동작 과정을 정리하면 다음과 같습니다.
- 인덱스
i는 마지막으로 선택된 활동을 가리킵니다. 처음에는 첫 번째 활동(인덱스 0)을 선택합니다. - 루프를 돌며 현재 활동
j의 시작 시간s[j]가 이전 활동의 종료 시간f[i]보다 크거나 같으면 두 활동이 겹치지 않으므로j번 활동을 선택하고i를j로 갱신합니다. - 이 과정을 모든 활동에 대해 반복하면 서로 겹치지 않는 최대 개수의 활동 집합을 얻을 수 있습니다.
예제 입력에서는 인덱스 0(시간 1~2)과 인덱스 1(시간 2~5)의 두 활동이 선택되었으며, 나머지 활동들은 앞서 선택한 활동과 시간이 겹쳐 제외되었습니다.
시간 복잡도
활동이 이미 종료 시간 기준으로 정렬되어 있다면 이 알고리즘은 O(n) 시간에 동작합니다. 정렬이 필요한 경우에는 O(n log n)의 시간 복잡도가 추가됩니다.
마무리
이 글에서는 그리디 알고리즘을 활용해 활동 선택 문제를 파이썬으로 해결하는 방법을 알아보았습니다. “종료 시간이 빠른 활동부터 선택한다”는 간단한 아이디어만으로 최적해를 보장받을 수 있다는 점이 이 문제의 핵심입니다. 회의실 배정, 강의 스케줄링 등 실생활의 다양한 일정 관리 문제에도 동일한 원리가 널리 적용되니 꼭 익혀두시기 바랍니다.