- 문제 링크
백준 1931번 - 회의실 배정
해결 전략
문제의 설명을 읽어보면 본 문제는 Dynamic Programming이나 Greedy Algorithm으로 다룰 수 있겠다는 느낌이 바로 든다. 그리고 좀 더 세세하게 문제 상황을 관찰해보면 어렵지 않게 Greedy Algorithm으로 해결할 수 있겠다는 감이 온다.
사실, 본 문제는 이미 학부 알고리즘 수업에서 한 차례 다룬 바 있는 Job Scheduling Problem의 한 종류에 해당한다. 각각의 일들의 시작 시간과 종료 시간이 주어지고, 그 사이에 다른 일이 중첩될 수 없을 때, 가장 최소, 혹은 가장 최다의 일 배치 수를 알아내는 문제 유형이다. 가장 대표적인 그리디 문제라고 배운 바 있다.
이러한 유형의 문제에 필요한 Greedy는 직접 찾아보아야 한다. 본 문제의 경우, 시작 시간과 종료 시간이라는 파라미터가 주어지기 때문에 이를 토대로 가장 본능적으로 해볼 수 있는 생각은 다음과 같다(엄밀히 보면 '시각'이란 표현이 맞다).
-
시작 시간을 기준으로 오름차순 정렬 후, 해당 배열을 Traverse하면서 각 종료 시간을 따져보자.
~> 좋은 접근이다. 하지만, 문제의 기본 예제에서도 발견할 수 있듯이, '각 종료 시간을 따지는 작업'이 상당히 복잡하고, 또한, N은 최대 100,000인 것을 고려하면 시간 초과가 날 것이 유력하다. 즉, 다른 접근이 가능한지를 더 생각해보는 것이 바람직하다. -
'(종료 시간) - (시작 시간)'을 기준으로 오름차순 정렬 후, 그 Duration이 짧은 item들부터 선택해 나간다. 이때, 기선택된 item들의 시간 관계를 침해하지 않는지 check하는 기능이 중요할 것이다.
~> 역시나 좋은 접근이다. 실제로 본인은 첫 문제 풀이 시도에 이 아이디어를 사용하였다. 굉장히 그럴듯하고, 주어진 기본 예제를 비롯해 많은 예시를 해결할 수 있다. 하지만, 가장 치명적인 반례가 하나 존재한다(본인은 첫 시도에서 이것을 생각치 못했다).
3
1 10
9 12
11 20
위의 예제의 경우, 2번 idea로 접근 시 정답인 2가 채택되지 않고, 오답인 1이 채택된다. 즉, Duration이 긴 item 사이에 Duration이 짧은 item이 중첩된 경우 이 2번 idea는 오답을 낸다.
1번 시도는 금새 폐기할 수 있지만, 2번 시도는 해볼만했다. 하지만, 결국 상기한 반례를 맞이하게 되면서 폐기될 것이다. 그렇다면 남아있는 아이디어는 무엇이 있을까? 아래를 보자.
- 1번과 2번 idea가 폐기되었으니, 이번엔 종료 시간을 기준으로 idea를 설계해보자. 우선 종료 시간을 정렬해보자. 주어진 기본 예제를 토대로 해보겠다.
11 11
1 4 1 4
3 5 3 5
0 6 0 6
5 7 5 7
3 8 3 8
5 9 5 9
6 10 6 10
8 11 8 11
8 12 8 12
2 13 2 13
12 14 12 14
(우측이 종료 시간 기준 정렬본이다.)
위에서부터 오름차순으로 차례대로 따져보자. 첫 번째 item은 전체 item 중 가장 종료 시간이 빠른 item이다. 이 친구를 픽하면 그 다음 가능한 친구는 (5, 7)이다. (5, 9)도 있지만, 최다 pick을 생각하면 정렬된 순서대로 (5, 7)을 그대로 취하는 것이 바람직해보인다.
이어서 픽 가능한 아이템은 (8, 11), (8, 12) 등인데, 역시나 같은 이유로 (8, 11)이 바람직하다. 그 다음은 (12, 14)가 pick해질 것이다.
(1, 4), (5, 7), (8, 11), (12, 14)
보아하니 Optimal Solution을 도출했다. 다른 예시들에 대해서도 통함을 곧바로 알 수 있다. 우연인 것일까? Greedy Algorithm의 Proof of Optimality를 간단히 검증해보자(엄밀한 수학적 증명 말고 직관적인 방식으로 확인한다).
- 첫 번째 pick되는 요소는 전체 요소 중 가장 종료 시간이 빠른 회의이다.
- 앞 요소 이후의 요소들 중, 앞 요소의 end time보다 시간적으로 더 뒤의 start time을 가지는 요소가 Algorithm에 의해 선택된다.
- 이는 남아있는 '가능 요소' 중에 가장 종료 시간이 빠른 회의이다.
- '종료 시간이 빠르다는 것'은 뒤에 배치해볼 수 있는 회의가 많다는 것이다.
- 남아있는 요소들 중 가장 종료 시간이 빠른 요소는 결국 남아있는 요소들 중 '앞으로 회의를 더 선택할 가능성이 가장 큰 요소'이기도 하다.
- 그말은 즉슨 본 Algorithm은 정당하다. 왜냐, 최다 개수의 회의를 배치해야하기 때문이다.
따라서 이 3번 idea를 기반으로 한 Greedy Algorithm은 본 문제의 Solution이다. 구현 과정은 상당히 간단하기 때문에 설명을 생략한다. 아래는 코드이다.
#include <iostream>
#include <algorithm>
// BOJ - 1931 Assign Conference Room
using namespace std;
typedef struct { int start, end; } Conf;
Conf arr[100000];
bool pred(Conf a, Conf b) {
if (a.end < b.end) return true;
else if (a.end == b.end && a.start < b.start) return true;
return false;
}
int solve(int n) {
int cnt = 0, j;
sort(arr, arr + n, pred);
for (int i = 0; i < n; ) {
for (j = i + 1; j < n; j++) {
if (arr[j].start >= arr[i].end) break;
}
i = j;
cnt++;
}
return cnt;
}
int main(void) {
int n;
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) { cin >> arr[i].start >> arr[i].end; }
cout << solve(n);
return 0;
}2번 Idea는 사실 반례를 맞이하기 전에 Proof of Optimality 판단 과정, 아니 그거까지 갈 필요도 없이 좀만 더 생각했으면 미리 폐기할 수 있었다. 2번 Idea의 Algorithm은 남아있는 회의들 중 가장 Duration이 짧은 회의를 pick한다. 근데 그 pick된 요소가 기선택된 요소들을 위배하는지 안하는지 알아야된다. 그말은 즉슨, Traverse에 중첩되는 Traverse가 하나 더 필요하다는 것이고, 앞서 말한 것처럼 N은 최대 100,000인 것을 고려하면 시간 초과가 예상되는 상황이다. 여기까지 판단하였으면 2번 Idea를 폐기하고 새로운 Idea를 고안했어야한다.
항상 자신이 설계한 알고리즘의 빅오를 고려해 시간 초과 여부를 미리 판단하고, 초과가 예상되면 과감하게 새로운 아이디어를 고안하자. 그것이 시간을 아끼는 지름길이다.
