Link: Lv4. 선입 선출 스케줄링
- 문제 설명
처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.
이 CPU는 다음과 같은 특징이 있습니다.
- CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
- 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
- 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.
처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때,
마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.
제한 사항
- 코어의 수는 10,000 이하 2이상 입니다.
- 코어당 작업을 처리하는 시간은 10,000이하 입니다.
- 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.
입출력 예
| n | cores | result |
|---|---|---|
| 6 | [1,2,3] | 2 |
입출력 예 설명
입출력 예 #1
처음 3개의 작업은 각각 1,2,3번에 들어가고, 1시간 뒤 1번 코어에 4번째 작업,
다시 1시간 뒤 1,2번 코어에 5,6번째 작업이 들어가므로 2를 반환해주면 됩니다.
- 문제 풀이
Case 1: Time을 증가시켜 가며 코어 전부를 검사
처음에는 시간에 흐름에 따라 코어 전체를 돌면서 검사하는 무식한 방법으로 풀었다.
예를들어 3개의 코어가 처리하는데 걸리는 시간이 각각 1, 2, 3 이고 작업 n 이 6이면
(time % core[i]) == 0 경우 작업을 하나씩 감해가면 되는 간단한 생각이다.
그러다가 n이 0이 되는 순간 해당 코어 번호를 반환하면 된다.
하지만 정확도 테스트는 통과하지만 효율성 테스트에 시간초과가 나고 만다.
시간 복잡도는 최악의 경우 BigO(n * core 개수) 근접할 것이다.
Case 2: 우선순위 큐를 이용
일반적인 큐는 first-in-first-out을 따르지만 우선순위 큐는 먼저 들어가도 최대값 혹은 최소값이 먼저 나온다.
일반적으로 얘기하는 최소 Heap, 최대 Heap 구조를 따른다. 참고로, C++ 우선순위 큐는 기본이 최대 Heap 이다.
필자는 최소 Heap이 필요하므로 greater<T> 를 추가하여 priority_queue를 생성하였다.
시작부터 전 코어에 작업이 할당되므로 n에서 코어 수만큼 빼주고 시작한다.
또한 Core 가 가진 고유 순서와 총 작업 시간이 함께 필요하므로 class corework로 만들어 우선순위 큐에 넣었다.
(처음 배열에 있던 Core 고유 순서를 반환해야 하기 때문이다.)
| 1 시간 | 2 시간 | 3 시간 | 4 시간 | 5 시간 | 6 시간 | |
| Core (2) | ||||||
| Core (3) | ||||||
| Core (4) |
최소 힙에 넣었으니 나오는 순서는 가장 빠른 Core(2)부터 나올 것이다.
근데 어짜피 2시간이 지나야 가장 빠른 Core(2)의 작업이 끝난다. 나머지 Core는 더 늦게 끝날 것이다.
이 말은 항상 최소 힙에 나오는 Core 처리 시간만큼 현재 시간을 워프(?)를 해도 괜찮다는 얘기다.
그리고 다시 워프한 현재 시간에 처리 시간을 더하여 Core(2)를 다시 우선순위 큐에 넣는다.
그리고 n이 0이 되는 순간의 Core의 고유 번호를 반환하면 된다.
주의할 점은, 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 해야 한다는 것이다.
시간 복잡도는 n(작업량) 만큼 반복문을 돌리기 때문에 BigO(n)이 될 것이다.
하지만 이 역시 문제가 개정되고 나서는 효율성 테스트 부분만 통과한다.
Case 3: Parametric Search를 이용
우선순위 큐로도 안되면 어떻게 해결해야지 고민하던 중에 Parametric Search를 이용하면 된다고 하는
어떤 분의 질문에 대한 답변을 보고 찾아 보았다. 기본은 Binary Search인데 약간 변형된 형태(?)라는 느낌이었다.
Parametric이라는 사전 뜻 자체가 “매개변수의” 라는 의미로 말 그대로 매개변수를 둬서 Binary Search 하는 것이었다.
그러면 어떤 것을 매개변수로 둬야 할까? 무엇이 Binary Search의 장점인 분할/정복의 매개변수로 쓸 수 있을까?
내가 생각해 본 것은 작업이 끝나는데 걸리는 총 작업시간 이었다. 정확히는 총 작업 시간에 따른 작업량이다.
만약 코어들 중 동일한 최소 작업시간 (ex. 2, 2, 2)로 가정 하고 최대는 (ex. 4, 4, 4)로 가정 하고 작업 량이 6이면
총 작업이 끝나는 시간은 (최소 작업시간 * (작업량 – 코어 개수)) / 코어 개수 이므로
최소 작업시간이 (2 * (6 – 3)) / 3 = 2 이고 최대 작업시간은 (4 * (6 – 3)) / 3 = 4 이 될 것이다.
그러면 실제 총 작업시간은 2시간 – 4시간 사이에 있게 된다.
실제로 위 예제로 해보면 (ex. 2, 3, 4)로 4시간으로 총 작업시간은 4시간이다.
| 최소 시간 | 중간 시간 | 최대 시간 |
| 2 시간 | 3 시간 | 4 시간 |
이제 최소 작업시간과 최대 작업 시간을 Binary Search를 해보면
중간 시간인 3시간 일 때 작업량은 (중간 시간 / 코어 처리 시간) 의 총 합이다. 이 작업량의 합을 현재 작업량이 하겠다.
그리고 (중간 시간 % 코어 처리 시간) == 0 인 경우는 중간 시간 시점에 작업을 마치고 새로 할당 받은 코어다.
이 현재 작업량이 n (총 작업량) 보다 작으면 최소 작업 시간을 중간 시간 으로 땡기고
반대로 n이 (현재 작업량 – 새로 할당 받은 코어 개수) 보다 작으면 최대 작업 시간을 중간 시간으로 땡긴다.
| 1 | 2 (현재 작업량 – 새로 할당 받은 코어 개수) | 3 |
| n | n | n |
위 그림 처럼 n 이 1에 있을 경우는 최대 시간을 중간 시간으로 내리고 n 이 3에 있을 경우 최소 시간을 중간으로 올린다.
만약 n이 2에 있을 경우에는 (현재 작업량에서 – 새로 할당 받은 코어 개수)를 한 작업량에서 부터 계산하여
n이 되는 시점의 해당 코어를 반환하면 된다. 시간 복잡도는 개선된 BigO(log n) 정도 일 것이다.
이 방법을 쓰면 효율성 테스트를 통과 할 수 있다.
Source Code: first_in_first_out_scheduling.cpp