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

활동 선택 (Activity Selection)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step
Activity Selection
A (1~3)
B (2~5)
C (4~6)
D (6~8)
E (5~9)
012345678910

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

Logic Node1 / 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)
Guide Progress0%