그리디 알고리즘 실전: 거스름돈과 회의실 배정 문제 분석

이론적으로 그리디 알고리즘의 정당성을 이해했다면, 이제 실전 문제에 적용하여 그 위력을 체감할 차례입니다. 그리디 알고리즘은 복잡한 점화식이나 상태 전이 테이블 없이도 문제를 해결할 수 있게 해주어, 적절한 상황에서 사용한다면 압도적인 코드 간결성과 실행 속도를 보장합니다. 본 포스팅에서는 그리디의 가장 고전적인 예제인 거스름돈 문제와 정렬의 마법이 발휘되는 회의실 배정 문제를 통해 실전 설계 능력을 배양해 보겠습니다.

1. 거스름돈 문제: 그리디가 승리하는 조건

편의점 계산대에서 거스름돈을 줄 때, 우리는 무의식적으로 가장 큰 단위의 화폐부터 내어줍니다. 이것이 바로 그리디 알고리즘입니다. 하지만 이 직관이 항상 옳은 것은 아닙니다. 거스름돈 문제에서 그리디가 정답을 보장하려면 '동전들 사이의 관계'가 매우 중요합니다.

1-1. 배수 관계의 중요성

한국의 화폐 단위인 500원, 100원, 50원, 10원은 각각이 서로의 배수 관계에 있습니다. 큰 단위의 동전은 항상 작은 단위 동전들의 합으로 정확히 대체될 수 있습니다. 이 경우, 큰 동전 하나를 쓰는 것이 작은 동전 여러 개를 쓰는 것보다 무조건 이득이기 때문에 그리디가 최적해를 보장합니다. 만약 동전 단위가 500원, 400원, 100원이라면 400원 두 개를 주는 것이 500원 한 개와 100원 세 개를 주는 것보다 효율적일 수 있으므로, 이때는 동적 계획법(DP)으로 선회해야 합니다.

2. 회의실 배정 문제: 활동 선택 문제(Activity Selection)

회의실 배정 문제는 한 개의 회의실을 여러 팀이 사용하고자 할 때, 시간대가 겹치지 않게 하면서 최대한 많은 회의를 배정하는 문제입니다. 이 문제는 그리디 알고리즘의 '선택 기준'이 얼마나 중요한지를 보여주는 대표적인 사례입니다. 단순히 회의 시간이 짧은 순서나 시작 시간이 빠른 순서로 선택하면 최적해를 얻지 못할 가능성이 큽니다.

2-1. 종료 시간(End Time) 기준의 탐욕적 선택

이 문제의 핵심 통찰은 '회의가 빨리 끝나야 다음 회의를 시작할 수 있는 여유가 생긴다'는 점입니다. 따라서 다음과 같은 그리디 전략을 수립합니다.

모든 회의를 종료 시간 기준으로 오름차순 정렬합니다. (종료 시간이 같다면 시작 시간 기준 정렬)
가장 먼저 끝나는 회의를 선택합니다.
이후 이전 회의의 종료 시간보다 시작 시간이 늦거나 같은 회의 중 가장 빨리 끝나는 것을 선택합니다.

이 전략은 매 순간 회의실을 가장 빨리 비워주는 결정을 내림으로써 전체 회의 개수를 극대화합니다. 이는 $O(N \log N)$의 정렬 시간만으로 최적해를 찾아내는 매우 효율적인 기법입니다.

3. 그리디 알고리즘 실전 적용 프로세스

실제 코딩 테스트나 실무 프로젝트에서 그리디 문제를 해결할 때는 다음의 루틴을 따르는 것을 추천합니다.

정렬(Sorting): 그리디 문제의 80% 이상은 정렬에서 시작합니다. 어떤 기준으로 정렬할지가 핵심입니다.
선택(Selection): 정렬된 순서대로 탐욕적 선택을 수행하며 조건에 맞는지 검사합니다.
해 소거(Reduction): 선택된 데이터가 이후의 선택 범위에 어떤 영향을 미치는지 파악하고 문제를 축소해 나갑니다.


# 회의실 배정 문제 Python 구현
def schedule_meetings(meetings):
    # 1. 종료 시간 기준 정렬, 같으면 시작 시간 기준
    meetings.sort(key=lambda x: (x[1], x[0]))
    
    count = 0
    last_end_time = 0
    
    for start, end in meetings:
        # 2. 이전 회의가 끝난 후 시작하는 회의 선택
        if start >= last_end_time:
            count += 1
            last_end_time = end
            
    return count

4. 그리디의 실무적 가치와 성능 분석

그리디 알고리즘은 탐색 범위가 기하급수적으로 넓은 NP-난해(NP-Hard) 문제들에 대한 근사치(Approximation)를 구할 때도 유용합니다. 비록 100% 완벽한 정답은 아닐지라도, 실무적으로 수용 가능한 수준의 해답을 순식간에 내놓기 때문입니다. 네트워크 라우팅 최적화, CPU 프로세스 스케줄링, 데이터 압축(허프만 코딩) 등에서 그리디는 여전히 가장 사랑받는 도구 중 하나입니다.

[그리디 실전 핵심 요약]
1. 거스름돈: 단위 간의 배수 관계가 성립할 때만 그리디가 최적해를 보장합니다.
2. 회의실 배정: 종료 시간 기준 정렬이라는 명확한 선택 기준이 전역 최적해를 이끌어냅니다.
3. 팁: 그리디는 정렬과 단짝입니다. 어떤 속성을 기준으로 정렬할지 찾는 것이 문제 해결의 시작입니다.

kguidebook0001 님의 블로그