yeolyi.com성열의 컴퓨터공학

그리디 알고리즘

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

회의실은 하나인데 회의 신청이 여럿 들어왔습니다. 시간이 겹치지 않게, 회의를 최대한 많이 넣고 싶습니다. 회의마다 넣거나 빼니, 회의가 n개면 모든 경우는 경우의 수로 2n가지입니다. 30개면 10억 가지가 넘습니다. 하나씩 보며 바로 넣을지 정할 수는 없을까요?

회의실 배정

방법은 간단합니다. 정한 순서대로 회의를 보며, 이미 잡은 회의와 겹치지 않으면 잡습니다. 어떤 순서로 볼지가 문제입니다.

고르는 순서
가
0~11시
나
1~4시
다
4~7시
라
7~10시
마
3~5시
바
6~8시
사
10~12시

볼 순서: 가, 나, 마, 다, 바, 라, 사

세 순서를 하나씩 골라 끝까지 진행해 봅시다.

일찍 시작하는 것부터 보면 가장 먼저 시작하는 긴 회의 하나가 하루를 다 차지해 1개뿐입니다. 짧은 것부터 보면 3개입니다. 짧은 회의가 두 회의 사이에 걸쳐 양쪽을 다 막기 때문입니다. 일찍 끝나는 것부터 보면 4개로 가장 많습니다.

이렇게 매 순간 지금 가장 좋아 보이는 것을 고르고 다시 돌아보지 않는 방법을 그리디 알고리즘(greedy algorithm)이라 합니다. 빠르고 단순하지만, 무엇을 “가장 좋다”고 보느냐에 따라 최선이 되기도 하고 아니기도 합니다.

위 회의를 일찍 끝나는 것부터 잡는 코드입니다. 먼저 회의를 선택 정렬로 end_time이 돌려준 값이 작은 것부터 늘어놓습니다.

1#include <stdio.h>
2
3struct Meeting {
4 int start;
5 int end;
6};
7
8struct Meeting meetings[7] = {
9 {0, 11}, {1, 4}, {4, 7}, {7, 10},
10 {3, 5}, {6, 8}, {10, 12}};
11
12int end_time(struct Meeting m) {
13 return m.end;
14}
15
16int main(void) {
17 // 선택 정렬로 일찍 끝나는 것부터
18 for (int i = 0; i < 7; i++) {
19 int min = i;
20 for (int j = i + 1; j < 7; j++) {
21 if (end_time(meetings[j]) <
22 end_time(meetings[min])) {
23 min = j;
24 }
25 }
26 struct Meeting t = meetings[i];
27 meetings[i] = meetings[min];
28 meetings[min] = t;
29 }
30 int last_end = 0;
31 for (int i = 0; i < 7; i++) {
32 struct Meeting m = meetings[i];
33 // 잡은 회의와 겹치지 않으면
34 if (m.start >= last_end) {
35 printf("%d~%d\n", m.start, m.end);
36 last_end = m.end;
37 }
38 }
39 return 0;
40}

변수 없음
출력 없음

end_time이 m.start를 돌려주게 고쳐 일찍 시작하는 것부터 보게 해 봅시다.

바꿔치기 증명

가장 일찍 끝나는 회의를 고르면 뒤에 남는 시간이 가장 깁니다. 이것이 늘 최선이라는 것은 다음처럼 증명합니다.

최선의 배정 하나가 있다고 합시다. 가장 일찍 끝나는 회의는 그 배정의 첫 회의보다 늦게 끝나지 않으니, 첫 회의를 이것으로 바꿔 넣어도 뒤 회의들과 겹치지 않습니다. 개수는 그대로이니 이것도 최선입니다. 남은 시간에 같은 논리를 되풀이하면, 일찍 끝나는 것부터 고른 답이 최선의 배정과 개수가 같아집니다.

그리디가 맞는다는 것은 이렇게 증명해야 합니다. 몇 번 맞았다고 늘 맞는 것은 아닙니다.

도전 문제

회의실 하나에 아래 회의 11개(시작~끝 시각)를 겹치지 않게 넣으려 합니다. 한 회의가 끝나는 시각에 다음 회의가 시작해도 됩니다. 최대 몇 개를 넣을 수 있을까요? 숫자로 답하세요.

1~4, 3~5, 0~6, 5~7, 3~9, 5~9,
6~10, 8~11, 8~12, 2~14, 12~16