2021 국가직9급 컴퓨터일반 7번 해설 — 탐욕 스케줄링
문제
아래와같은순서대로회의실사용요청이있을때, 다음중 가장많은회의실사용시간을확보할수있는스케줄링방법은? (단, 회의실은하나이고, 사용요청은(시작시각, 종료시각)으로 구성된다. 회의실에특정회의가할당되면이회의시간과겹치는 회의요청에대해서는회의실배정을할수없다) (11 : 50, 12 : 30), ( 9 : 00, 12 : 00), (13 : 00, 14 : 30), (14 : 40, 15 : 00), (14 : 50, 16 : 00), (15 : 40, 16 : 20), (16 : 10, 18 : 00)
- ① 시작시각이빠른요청부터회의실사용이가능하면확정한다
- ② 종료시각이빠른요청부터회의실사용이가능하면확정한다
- ③ 사용요청순서대로회의실사용이가능하면확정한다
- ④ 회의시간이긴요청부터회의실사용이가능하면확정한다 ← 정답
선지별 해설
① 시작시각이빠른요청부터회의실사용이가능하면확정한다
이 선지 진술은 틀림(X)
시작 시각 기준으로 고르면 총 330분 수준에 머문다. 이 사례에서는 회의시간이 긴 요청부터 선택할 때 더 긴 총 사용시간을 얻는다.
② 종료시각이빠른요청부터회의실사용이가능하면확정한다
이 선지 진술은 틀림(X)
종료 시각 기준은 보통 회의 개수 최대화에 쓰이는 기준이다. 이 문제의 목적은 총 사용시간 최대화이며, 주어진 입력에서는 최적이 아니다.
③ 사용요청순서대로회의실사용이가능하면확정한다
이 선지 진술은 틀림(X)
요청 순서 기준은 앞에 온 짧은 회의를 먼저 잡아 이후 긴 회의를 놓칠 수 있다. 제시된 입력의 최대 사용시간 기준은 회의시간 길이이다.
④ 회의시간이긴요청부터회의실사용이가능하면확정한다
이 선지 진술은 옳음(O)
긴 회의부터 배정하면 9:00-12:00, 13:00-14:30, 14:40-15:00, 16:10-18:00을 잡아 총 400분을 확보한다. 다른 제시 기준보다 총 사용시간이 크다.
핵심 요약 (Q&A)
- Q. 2021 국가직9급 컴퓨터일반 7번의 핵심 쟁점은 무엇인가?
- A. 2021 국가직9급 컴퓨터일반 7번은 탐욕 스케줄링에 관한 문항으로, "옳은 것"을 고르는 문제입니다.
- Q. 2021 국가직9급 컴퓨터일반 7번의 정답은?
- A. 정답은 ④번입니다. 긴 회의부터 배정하면 9:00-12:00, 13:00-14:30, 14:40-15:00, 16:10-18:00을 잡아 총 400분을 확보한다. 다른 제시 기준보다 총 사용시간이 크다.