7-10. 그리디: Minimum Number of Platforms

1. 플랫폼 최소 개수 문제: 기차 운행 스케줄링의 최적화

기차 운행 스케줄링 문제는 현실 세계에서 매우 중요한 문제 중 하나입니다. 각 기차의 도착 및 출발 시간을 고려하여 최소한의 플랫폼으로 모든 기차를 수용하는 것은 자원 효율성을 극대화하고 운영 비용을 절감하는 데 기여합니다. 이 문제는 "Minimum Number of Platforms" 문제로 알려져 있으며, 그리디 알고리즘을 사용하여 효율적으로 해결할 수 있습니다.

그리디 알고리즘은 각 단계에서 최적의 선택을 함으로써 전체 문제에 대한 최적의 해를 구하는 알고리즘입니다. 이 문제에서는 각 기차의 도착 및 출발 시간을 정렬하고, 현재 플랫폼의 사용 가능 여부를 확인함으로써 최소 플랫폼 개수를 결정합니다.

2. 문제 정의 및 예시

기차 시간표는 각 기차의 도착 시간과 출발 시간의 쌍으로 주어집니다. 목표는 모든 기차를 수용하기 위해 필요한 최소 플랫폼 수를 계산하는 것입니다. 기차는 한 플랫폼에서 출발하기 전에 도착해야 하며, 두 기차가 같은 플랫폼을 사용하려면 시간 간격이 겹치지 않아야 합니다.

예를 들어, 다음과 같은 기차 시간표가 주어졌다고 가정해 보겠습니다.

이 경우, 최소 3개의 플랫폼이 필요합니다.

3. 그리디 알고리즘의 핵심 원리

이 문제를 해결하기 위해 그리디 알고리즘을 사용하는 핵심 원리는 다음과 같습니다.

1. 도착 시간과 출발 시간 정렬: 모든 기차의 도착 시간과 출발 시간을 정렬합니다.

2. 이벤트 처리: 정렬된 시간 순서대로 각 이벤트를 처리합니다. 이벤트는 도착 또는 출발입니다.

   • 도착 이벤트: 새로운 기차가 도착하면, 플랫폼이 필요한지 확인합니다. 현재 사용 중인 플랫폼 수가 최소 플랫폼 개수보다 작으면 플랫폼 수를 증가시킵니다.
   • 출발 이벤트: 기차가 출발하면, 해당 플랫폼을 사용할 수 있게 됩니다.

3. 최대 동시 사용 플랫폼 수: 모든 이벤트를 처리하는 동안, 동시에 사용 중인 플랫폼의 최대 개수가 최소 플랫폼 개수가 됩니다.

이 알고리즘은 각 단계에서 지역적으로 최적의 선택을 함으로써 전체적으로 최적의 해를 보장합니다.

4. 알고리즘 구현 상세

1) 데이터 구조

우선, 기차의 도착 시간과 출발 시간을 저장하기 위한 적절한 데이터 구조가 필요합니다. 일반적으로, 두 개의 배열 또는 리스트를 사용하여 각 기차의 도착 시간과 출발 시간을 저장할 수 있습니다. 또는, 시간과 해당 이벤트(도착 또는 출발)를 나타내는 하나의 배열 또는 리스트를 사용할 수도 있습니다.

2) 정렬

알고리즘의 첫 번째 단계는 도착 시간과 출발 시간을 정렬하는 것입니다. 정렬은 효율적인 알고리즘을 사용해야 합니다. 퀵 정렬, 병합 정렬 또는 힙 정렬과 같은 $O(n \log n)$ 시간 복잡도를 가지는 정렬 알고리즘을 사용하는 것이 좋습니다.

3) 이벤트 처리

정렬된 시간 순서대로 각 이벤트를 처리합니다.

• 도착 이벤트:
  • 현재 사용 중인 플랫폼 수를 증가시킵니다.
  • 최대 플랫폼 개수를 업데이트합니다.
• 출발 이벤트:
  • 현재 사용 중인 플랫폼 수를 감소시킵니다.

4) 최소 플랫폼 개수

모든 이벤트를 처리한 후, 알고리즘은 최소 플랫폼 개수를 반환합니다.

5. 코드 예시 (Python)

def min_platforms(arrivals, departures):
    """
    기차 시간표를 기반으로 최소 플랫폼 개수를 계산합니다.

    Args:
        arrivals: 기차 도착 시간 리스트.
        departures: 기차 출발 시간 리스트.

    Returns:
        최소 플랫폼 개수.
    """

    # 1. 도착 및 출발 시간 정렬
    arrivals.sort()
    departures.sort()

    platforms_needed = 0  # 현재 사용 중인 플랫폼 수
    max_platforms = 0  # 최대 플랫폼 수
    arrival_index = 0
    departure_index = 0

    # 2. 이벤트 처리
    while arrival_index < len(arrivals) and departure_index < len(departures):
        # 도착 시간이 출발 시간보다 빠르면
        if arrivals[arrival_index] <= departures[departure_index]:
            platforms_needed += 1  # 플랫폼 필요
            arrival_index += 1
            max_platforms = max(max_platforms, platforms_needed)
        # 출발 시간이 도착 시간보다 빠르면
        else:
            platforms_needed -= 1  # 플랫폼 사용 종료
            departure_index += 1

    # 3. 최소 플랫폼 개수 반환
    return max_platforms

# 예시 사용
arrivals = [900, 940, 950, 1100, 1200, 1230]
departures = [940, 1200, 1100, 1230, 1300, 1400]
result = min_platforms(arrivals, departures)
print(f"필요한 최소 플랫폼 개수: {result}")

6. 알고리즘 분석

1) 시간 복잡도

알고리즘의 시간 복잡도는 주로 정렬 단계에 의해 결정됩니다. 도착 시간과 출발 시간을 정렬하는 데 $O(n \log n)$ 시간이 걸립니다. 그 후, 정렬된 시간 목록을 순회하면서 각 이벤트를 처리하는 데 $O(n)$ 시간이 걸립니다. 따라서 전체 시간 복잡도는 $O(n \log n)$입니다.

2) 공간 복잡도

공간 복잡도는 입력 데이터의 크기에 따라 달라집니다. 시간 배열을 저장하는 데 $O(n)$ 공간이 필요합니다. 따라서 공간 복잡도는 $O(n)$입니다.

7. 응용 및 확장

이 문제는 기차 운행 스케줄링뿐만 아니라 다른 스케줄링 문제에도 적용될 수 있습니다.

• 회의실 예약: 회의 시간표를 기반으로 최소 회의실 개수를 결정하는 데 사용될 수 있습니다.
• 작업 스케줄링: 작업의 시작 시간과 종료 시간을 고려하여 최소 작업 공간 또는 자원을 결정하는 데 사용될 수 있습니다.
• 데이터 센터 서버 관리: 서버가 처리해야 하는 요청의 시작 시간과 종료 시간을 고려하여 최소 서버 개수를 결정하는 데 사용될 수 있습니다.

8. 주의사항 및 트러블 슈팅

• 입력 데이터: 도착 시간과 출발 시간이 정확하게 주어졌는지 확인해야 합니다. 오류가 있는 경우 알고리즘이 올바르게 작동하지 않을 수 있습니다.
• 동시 도착 및 출발: 동일한 시간에 도착과 출발이 발생하는 경우, 먼저 출발 이벤트를 처리해야 합니다. 이렇게 하면 플랫폼이 가능한 한 빨리 해제되도록 보장합니다.
• 시간 형식: 시간 표현 형식이 일관성이 있는지 확인합니다. 24시간 형식 또는 오전/오후 형식과 같은 다양한 시간 형식을 처리하는 방법을 고려해야 합니다.

9. 결론

"Minimum Number of Platforms" 문제는 그리디 알고리즘을 사용하여 효율적으로 해결할 수 있는 스케줄링 문제입니다. 이 문제의 해결 과정은 그리디 알고리즘의 개념을 이해하고, 실용적인 문제에 적용하는 좋은 예시를 제공합니다. 이 알고리즘을 이해하고 구현함으로써, 실제 세계의 다양한 스케줄링 문제를 해결하는 데 필요한 기초 지식을 얻을 수 있습니다.