1931번: 회의실 배정(python)

 

문제 접근

 

첫번째 접근(시간초과)

그리디 알고리즘에 익숙치 않던 나는 문제 접근 자체에서 틀려버렸다. 재귀 호출을 통해 모든 스케줄링 경우의 수를 배열에 넣고 max값을 구했는데 역시나 시간초과가 떴다.

import sys

def scheduling(idx, cnt, arr):
    if idx >= n - 1:
        arr.append(cnt)
        return cnt
    for i in range(idx, n):
        if meetings[idx][1] <= meetings[i][0]:
            cnt += 1
            idx = i
            scheduling(i, cnt, arr)


n = int(sys.stdin.readline())
meetings = []
for _ in range(n):
    start_end = list(map(int, sys.stdin.readline().split()))
    meetings.append(start_end)
meetings.sort()
array = []


for i in range(n - 1):
    scheduling(i, 1, array)

print(max(array))

두번째 접근(성공)

N(1 ≤ N ≤ 100,000)인 배열에 2초의 시간제한이라면 시간 복잡도가 O(N^2)이 되는 순간 시간초과가 뜨는 것은 당연하다. 그렇다면 단 한번의 순회만으로 답을 찾아야 하는데, 그러려면 정렬된 배열에서 최적의 선택을 하는 공식을 정해야 한다. 

먼저, 종료 시간이 빠른 순으로 선택해가고, 종료 시간이 같을 경우 시작 시간이 빠른 것을 선택하는 식으로 구성하였다. 쉽게 말해, 정렬을 하되 1) 종료 시간 오름차순 2)시작 시간 오름차순으로 정렬 후, 종료시간을 체크해가며 cnt 변수를 증가시키는 방식으로 풀어나갈 수 있다.

답안 코드는 다음과 같다.

import sys

n = int(sys.stdin.readline())
time_table = []
for i in range(n):
    schedule = list(map(int, sys.stdin.readline().split()))
    time_table.append(schedule)

time_table.sort(key=lambda x: x[0])
time_table.sort(key=lambda x: x[1])


cnt = 1
end = time_table[0][1]
for i in range(1, n):
    if end <= time_table[i][0]:
        end = time_table[i][1]
        cnt += 1
print(cnt)

 

마치며

그리디(탐욕적) 알고리즘이란 말 그대로 눈 앞에 놓인 최적의 상황을 쫓아가는 것이다. 알고리즘 특성상 그리디로 푼 문제의 정답이 최적해임을 증명하는 것은 어려운 일인 것 같다. 아니나 다를까, 그리디에 관한 많은 포스팅에서 방법만 알면 쉽게 구현할 수 있는 반면 그것을 증명하는 것은 매우 어려운 일이라고 언급하고 있다. 이러한 그리디 알고리즘을 증명하는 여러가지 방법론이 존재하는 듯 한데, 시간이 되면 조금 해당 알고리즘을 증명하는 방법에 대해 더 깊게 공부해보고 포스팅할 계획이다.