Oh My Algorithm
Algorithm Guidecomplexity: O(n log n)

활동 선택 (Activity Selection)

끝나는 시각이 빠른 활동부터 고르면 겹치지 않는 활동을 가장 많이 선택할 수 있다는 그리디 문제입니다. 종료 시각 기준으로 정렬한 뒤 직전 활동과 겹치지 않는 것만 차례로 채택합니다.

01활동 선택 (Activity Selection)

끝나는 시각이 빠른 순으로 정렬한 활동들입니다. 시간이 겹치지 않게 최대한 많이 고르는 것이 목표입니다.

가장 먼저 끝나는 A(1~3)를 고릅니다. 이제 다음 활동은 3시 이후에 시작해야 합니다.

B는 2시에 시작해 A가 끝나기 전에 걸칩니다. 건너뜁니다.

C는 4시 시작이라 A와 겹치지 않습니다. 골라 두면 다음 기준은 6시가 됩니다.

D는 정확히 6시에 시작합니다. 겹치지 않으니 고르고, 기준을 8시로 옮깁니다.

E는 5시 시작이라 D가 끝나기 전에 걸칩니다. 건너뜁니다.

선택 완료 · A · C · D 세 개. 끝나는 시각이 빠른 것부터 고르면 항상 최대 개수를 보장합니다.

A (1~3)
B (2~5)
C (4~6)
D (6~8)
E (5~9)
012345678910
1 / 7

02 쉽게 이해하기

For Everyone
🔑핵심 동작

끝나는 시각이 이른 것부터 고르면 뒤에 남는 시간이 가장 많아져 최대 개수를 담을 수 있습니다.

💡쉽게 말하면

끝나는 시각이 빠른 활동부터 고르고, 직전에 고른 것과 겹치지 않는 것만 차례로 선택합니다.

이 단순한 규칙만으로 최대 개수가 보장돼요.

📍어디에 쓰나
  • –회의실·강의실 배정
  • –작업 스케줄링

03 파이썬 구현 코드

활동 선택 (Activity Selection)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py
def activity_selection(activities):
    # activities: [(start, finish), ...]
    activities.sort(key=lambda a: a[1])
    selected = [activities[0]]
    last_finish = activities[0][1]
    for start, finish in activities[1:]:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish
    return selected

04 자주 묻는 질문

FAQ
활동 선택 (Activity Selection)란 무엇인가요?+

끝나는 시각이 빠른 활동부터 고르면 겹치지 않는 활동을 가장 많이 선택할 수 있다는 그리디 문제입니다. 종료 시각 기준으로 정렬한 뒤 직전 활동과 겹치지 않는 것만 차례로 채택합니다.

활동 선택 (Activity Selection)의 시간복잡도는 어떻게 되나요?+

활동 선택 (Activity Selection)의 시간복잡도는 O(n log n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

활동 선택 (Activity Selection)은(는) 어디에 사용하나요?+

회의실·강의실 배정, 작업 스케줄링.

활동 선택 (Activity Selection)를 쉽게 비유하면?+

끝나는 시각이 이른 것부터 고르면 뒤에 남는 시간이 가장 많아져 최대 개수를 담을 수 있습니다.

→ 그리디 전체 보기Related
🎯동전 거스름돈 (Coin Change)
O(n)
🎯허프만 코딩 (Huffman Coding)
O(n log n)