[컴퓨팅사고력] 회의실을 최대 몇팀에게 배정을 해 줄 수 있을까요?

원당이 아빠는 회사에서 회의실을 관리하는 관리자 입니다.

아빠가 회사에서 회의실을 사용하겠다는 회의실 신청서를 가져 왔는데~

신청 한 사람이 많아서 누군가의 신청서는 반려해야 합니다.

아빠는 최대한 많은 팀이 회의실을 사용하기를 원하고 최소의 팀에게 신청서를 반려 하고 싶습니다.

신청서가 다음과 같다면 몇팀을 배정하고 몇팀을 반려하는 것이 최선인지 찾아 주세요.

단 끝나는 시간에 딱 맞춰 다른 팀이 들어 갈 수 있다고 가정 합니다.

회의팀	시작시간	끝나는시간
1	3	5
2	1	4
3	2	13
4	5	9
5	5	7
6	1	6
7	8	11
8	8	12
9	12	14

 

문제풀이)

맨 처음 2번 팀을 배정 하면 4시에 끝납니다. 그 다음 5번 팀을 배정 하면 7시에 끝납니다. 그 다음 7번 팀을 배정 하면 11시에 끝납니다. 그 다음 9번 팀을 배정하면 14시에 끝납니다. 이렇게 2,5,7,9 번팀을 배정하고 나머지 팀의 신청서를 반려 합니다.

 

컴퓨팅 사고력

컴퓨팅 과학에서 그리디 알고리즘의 대표적인 문제로 회의실 배정 문제를 생각해 볼 수가 있습니다.

하나의 회의실을 여러팀이 신청 했을때 가장 많은 팀이 사용하려고 하면 겹치지 않게 최대한 배정을 하고 배정을 하지 못한 팀에게는 신청서를 반려 해야 합니다.

물론 요즘처럼 시스템이 잘 되어 있다고 하면 실시간으로 먼저 선점 하도록 시스템이 되어 있겠지만 어떤 한 팀이 1시부터 24시까지 회의실을 예약하면 다른 팀이 회의실을 전혀 사용할 수 없는 문제가 발생하기 때문에 이런 경우에도 또 다른 보완책이 있어야 하겠네요.^^

위의 문제는 끝나는 시간순으로 정렬해서 먼저 끝나는 팀을 배정해 주고 이어서 배정을 해 줄 수 있는 팀을 배정을 해 주는 그리디 알고리즘으로 해결을 할 수가 있습니다.

회의팀	시작시간	끝나는시간
2	1	4
1	3	5
6	1	6
5	5	7
4	5	9
7	8	11
8	8	12
3	2	13
9	12	14

 위와 같이 끝나는 시간 순으로 정렬 한 후에 2번팀을 배정하고 4시에 끝나므로 4보다 큰 수로 시작하는 팀 중에 가장 먼저 만나는 5번팀을 배정 해 주면 두 팀이 회의를 끝났을때 7시가 됩니다. 따라서 8시에 시작하는 7번팀을 배정하고 11시에 끝나면 12시에 시작하는 9번팀을 배정 할 수가 있게 됩니다.

이렇게 자신의 차례에서 선택이 가능하면 선택을 하는 알고리즘을 그리디 알고리즘이라고 합니다.

이러한 그리디 알고리즘은 일반적으로 문제의 제약조건을 만족하면서 최대 혹은 최소로 하는 해를 구하는 동전교환, 회의실배정,스케줄링,최단경로 등의 문제에서 다양하게 사용되고 있습니다.