[백준 알고리즘: python 3] #1931 - 회의실 배정 (Greedy 알고리즘 스터디)

 

https://www.acmicpc.net/problem/1931

 

이번 문제는 Greedy 알고리즘에 대한 개념을 공부하기 위해 선정된 1931번 회의실 배정 문제입니다. Greedy 알고리즘이 이름이 생소해서 시간이 좀 걸릴까 했는데, 개념 자체는 그렇게 어렵지 않고 그 개념을 그대로 이해해서 풀 수 있는 문제여서 적절히 잘 배운 것 같습니다.

 

Greedy 알고리즘, 탐욕 알고리즘은 매 순간마다 최적의 답을 찾아가는 알고리즘입니다. 보통 이전에 리뷰한 Dynamic Programming(DP)과 비교가 되곤 하는데요, 되도록 모든 경우에 대해 탐색을 해서 전체의 해결책을 찾는 DP와는 달리 탐욕 알고리즘은 지금 당장의 분기마다 최적의 답만 찾아간다는 것이 다릅니다. 1분의 시간이 있는데, 지금 당장 바나나를 3개 먹거나 1분만 기다리면 바나나 4개를 먹을 수 있는 상황에 탐욕 알고리즘은 1분 뒤의 상황은 생각하지 않고 당장 바나나를 3개 먹어버리는 것이지요. 즉, 지금 당장의 최적의 답은 구했지만, 전체적인 상황(1분이 지난 상황)을 보면 최적의 답을 구했다고 보기는 어렵습니다.

 

그렇다면 탐욕 알고리즘은 쓸데가 없는 그냥 욕심많은 알고리즘일 뿐일까요? 그것은 아닙니다. 우선, 모든 상황을 고려(1분 뒤에 먹을 수 잇는 바나나 최대량을 계산하는 것)하는 것보단 연산 속도가 빠르기도 하고, 탐욕 알고리즘을 사용해서 풀 수 있는 문제도 존재하기 때문입니다. 이번 회의실 배정 문제가 대표적인 예시 중 하나입니다.

 

회의실 배정 문제는 한정된 시간안에 한 회의실에서 주어진 회의 일정을 최대한 많이 배정하는 문제입니다. 회의들은 서로 시간이 겹칠 수가 있고, 시간이 겹쳐버리면 그 중 하나의 회의 밖에는 진행할 수 없습니다. 처음 문제를 접할 때 풀이가 복잡할 것이라고 생각할 수 있겠지만 바로 직관적으로 생각해보면, 앞선 회의들이 그저 빨리 끝나는 것이기만 하면 됩니다. 그러면, 뒤의 회의를 최대한 많이 잡을 수 있으니까요.

 

문제에서 주어진 예시를 생각해봅시다.

 

 

 

총 11개의 회의 일정이 있고, 왼쪽 값은 시작 시간, 오른쪽 시간은 종료 시각입니다. (편의상 시간단위는 '시'라고 하겠습니다.) 우선, 처음 시작(0시)시에 가장 먼저 끝나는 회의는 1시에 시작해서 4시에 끝나는 회의입니다. 그럼 그 회의를 배정하고, 4시에 끝나니까 시작 시간이 4시 전인 회의는 모두 배정하지 않고 그 다음으로 가장 빨리 끝나는 회의를 고릅니다. 5시에 시작하고 7시에 끝나는 회의겠네요. 다음 회의는 7시 전에 끝나지 않고 가장 빨리 끝나는 회의를 고르면 됩니다.

 

Hint!

탐욕 알고리즘은 이런식입니다! 그럼 탐색이 많아질 수도 있겠네요. 그래서 종료 시각, 시작 시각 순으로 정렬을 한 뒤에 앞에서부터 가장 빨리 끝나는 회의를 배정하고 그 다음 가장 빨리 끝나는 회의를 배정하는 탐욕 알고리즘을 한 번의 알고리즘으로 수월하게 적용할 수 있습니다. 이 경우, 종료 시각만을 가지고 정렬하여 탐욕 알고리즘을 적용하게 되면 아마도 다음 반례를 해결하지 못할 것입니다. 이 경우의 답은 6입니다.

 

9 
8 8 
5 8
3 4
2 5 
2 7
8 8
1 10
3 3
10 10

 

종료 시각이 8인 회의들의 정렬이 잘 되지 않기 때문입니다. `(8, 8), (5, 8), (8, 8)` 로 정렬이 되면 탐욕 알고리즘은 루프를 돌다가 (5, 8)을 배정하지 않고 (8, 8)을 먼저 배정하기 때문이에요. 그래서 저한테는 2중 정렬(?)을 하는 방법을 찾아보는 것이 중요했네요..ㅎㅎ

 

아래의 코드로 성공했습니다.

import sys

N = int(sys.stdin.readline())

schedules = []
timer = 0
for _ in range(N):
    s = tuple(map(int, sys.stdin.readline().replace("\n", "").split()))
    schedules.append(s)

selected = []
# 종료 시각 -> 시작 시각 순으로 정렬
schedules = sorted(schedules, key=lambda x: (x[1], x[0]))
for schedule in schedules:
    if schedule[0] < timer: continue
    selected.append(schedule)
    timer = schedule[1]

print(len(selected))