안녕하세요! 쏘코입니다.
야심한 새벽에 한문제만 풀고 자려고 했는데.. 망했습니다. 중간에 딴짓을 좀 하긴 했지만 어쨌든 2~3시간 부었는데, 테스트케이스를 잘못 넣어서 한 1시간 정도는 삽질한 문제였습니다..
목차
0. 문제 설명
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.
예를 들어
- 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청
와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.
한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.
- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms) - B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms) - C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)
이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.
하지만 A → C → B 순서대로 처리하면
- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms) - C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms) - B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)
이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)
0.0. 제한 사항
- jobs의 길이는 1 이상 500 이하입니다.
- jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
- 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
- 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
- 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
0.1. 입출력 예
| jobs | return |
| [[0, 3], [1, 9], [2, 6]] | 9 |
0.2. 입출력 예 설명
문제에 주어진 예와 같습니다.
- 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
- 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
- 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.
1. 풀이 과정
보자마자 이거 운영체제인데???? 라는 생각이 들었습니다.
불과 저번 학기(20-2학기)에 들었던 내용이 문제로 나오니까 참 반가웠습니다.
그림을 통해 가장 먼저 파악했던 것은 비선점형 방식이었습니다. 또한 평균 대기시간을 최소화시키는 것이 목적이었기 때문에 SJF(Shortest Job First)방식을 사용하면 되겠다는 생각을 했습니다. 실제로 SJF는 작업이 완료하는 데 얼마나 걸릴 지 모르기 때문에 현실적인 스케줄링 방법은 아니지만(물론 예측기법을 통해 어느 정도 실현 가능하긴 하다) 이 문제에서 입력값으로 모든 프로세스의 요청시간과 작업시간을 받기 때문에 SJF를 사용할 수가 있습니다.
빠르게 파악을 했으니 이제 구현만 하면 되는데, SJF를 구현하는 과제에서 구글에 큰 도움을 받았던 저는 쉽게 구현하지를 못했습니다. 다 풀고 나서 찾아보니 Preemptive SJF(선점형 SJF)는 구현했는데 Non-preemptive SJF(비선점형 SJF)는 구현하지 않았더라구요. 아무리 그래도 그렇지 Preemptive방식보다 Non-preemptive방식이 구현하기가 훨씬 쉬운데(교수님 피셜) 구현을 하는데 애를 먹었다는 사실이 조금 부끄러웠습니다. (이때는 heap이나 vector가 아닌 struct를 사용해서 구현했습니다)
이번 포스팅은 운영체제 포스팅이 아니기 때문에, 더 자세히 알고 싶으시다면 아래 링크에 제 네이버 블로그에 정리해둔 글이 있으니 참고하시면 도움이 될 수도 있습니다!
[운영체제] ch5 Process Scheduling
수강하는 과목에는 여러 개의 과제가 쌓여있으면과제 하나하나가 Process이고과제 중에 어떤 걸 먼저 하냐...
blog.naver.com
아무튼 저는 시간 변수인 t, min-heap을 사용하기 위한 primary queue(ready queue라고 볼 수 있겠네요), primary queue에 들어간 작업의 수를 나타내는 변수인 cnt, 현재 작업중인 요소를 담은 rq(running queue라고 볼 수 있겠습니다)를 만들었습니다. 마지막으로 진행중인 작업의 진행을 보여주는 work변수도 만들었습니다. 지금 와서 생각해보면 pq로 들어간 작업의 수(cnt)보다는 완료한 작업의 수를 나타내는 변수를 만드는 것이 훨씬 좋았겠네요. (괜히 while문의 조건이 복잡해졌습니다 ㅠ 아래 소스 코드에서는 cnt를 수정한 버전도 같이 올려뒀습니다!)
특정 시간이 되면 그 시간이 요청 시간인 작업들을 pq에 넣었습니다. 그리고 어떤 작업이 pq에 들어가는 순간 cnt를 하나 증가시킵니다. 같은 시간에 들어가는 작업이 여러개면 그만큼 cnt도 증가하게 만들었습니다.
아, pq에 넣을때는 그대로 넣으면 second를 정렬하기 위해서 별도의 함수를 만들어야 했기 때문에 귀차니즘을 최소화하기 위해서 first와 second의 위치를 바꿔서 넣어줬습니다. job에서는 [작업의 요청 시간, 작업의 소요시간] 이었지만 pq와 rq에서는 [작업의 소요시간, 작업의 요청시간]이 된 것이죠.
그 다음엔 완료된 작업을 빼줬습니다. answer에다가 현재 시간인 t에서 요청 시간인 rq.second를 뺀 시간을 더해줍니다. (이걸 좀 있어보이게 말하면 turnaround time(반환시간)이라고 합니다. [burst time(수행시간) + waiting time(대기시간)], 혹은 [completion time(완료시간) - arrival time(도착시간)]으로 나타낼 수 있습니다.)
빼줬으니 running queue와 work(작업량)도 다시 초기화해줘야겠죠.
이렇게 rq를 비웠는데 pq가 비어있지 않다면 rq에 새로운 친구를 넣어줍니다. 바로바로 일해야 빠릿빠릿하게 진행될테니까요! rq(running queue)에다가 pq(ready queue)의 꼭대기에 있는 작업시간이 가장 짧은 min_heap을 넣어주고 그걸 pq에서 빼줍니다.
이제 새로운 친구가 왔으니 작업을 시작해야겠죠. 작업량과 시간을 1씩 증가시킵니다.
만약 pq가 비었는데 rq도 비었다? 그럼 work없이 시간만 증가시킵니다.
이 과정을 모든 작업이 완료될 때까지 반복합니다. 저같은 경우에는 pq에 들어간 요소를 카운트했기 때문에 별도로 running queue가 비어야 한다는 조건을 넣어줬는데, 위에서 말했다시피 완료한 작업의 수를 카운트하면 보다 간단하게 만들 수 있을 것 같습니다.
모든 작업이 끝나면 answer를 일의 수인 size로 나눠줍니다. size()를 매번 쓸 수도 있지만 개인적으로 자주 쓰는 size()의 경우 따로 저장해놓습니다. 쓰기도 편하고 계산 과정도 단축되는 것 같은 효과가 있거든요. (실제 효과는 거의 없다고 보시는게 맞습니다. size()를 뜯어보면 for문을 돌리거나 하는게 아니라 따로 값을 저장해놓는 형태이기 때문이죠.)
제 풀이의 Big-O notation은 O(n)입니다. 조금 엄밀히 말하면 O(tn)이 되겠네요. while문이 t만큼 돌아갑니다.
아, 테스트 케이스를 잘못써서 시간을 날렸다고 했는데,
테스트 2를 예로 들면 저는 (2+3)/2가 2.5니까 2가 나올거라고 생각하고 테스트 3은 (3+12)/2해서 7.5니까 7이 나올거라 생각하고 테스트 4는 (4+12+111)/3해서 42.33이니까 42가 나올거라고 생각했습니다. 알고보니 (2+(3-1))/2, (3+(12-1))/2, (4+(12-2)+(112-3))/3 해야하더라구요..?! 집중력이 떨어졌나봅니다 ㅠ
2. 소스 코드
2.0. 처음 통과한 버전
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<vector<int>> jobs) {
int answer = 0;
int t = 0; // 시간
int cnt = 0; // 들어간 작업의 수
int size = jobs.size();
int work = 0; // 현재 진행중인 작업의 작업량
pair<int,int> rq = {0,0}; // 작업중인 job의 상태 [작업량, 요청시간]
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 작업시간을 담은 pq
while (!(cnt == size && rq.first == 0 && rq.second == 0)){
for (int i = 0; i < size; ++i){
if (jobs[i][0] == t){
pq.push(make_pair(jobs[i][1], jobs[i][0])); // 요청받으면 ready queue에 올라감, cmp 함수 따로 만들기 귀찮아서 위치를 바꿔서 pq에 넣음
++cnt;
}
}
// 완료된 작업 빼주기
if (rq.first != 0 && work == rq.first){
answer += (t - rq.second);
rq = {0,0};
work = 0;
}
// pq가 비어있지 않은데 rq가 비어있으면
if (!pq.empty() && rq.first == 0){
rq = pq.top(); // running queue에 pq에서 가장 작업시간이 짧은 친구를 데리고옴
pq.pop();
}
if (!rq.first == 0) { // 작업 진행
++work;
++t;
}
else
++t;
}
answer /= size;
return answer;
}
2.1 cnt 수정버전
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<vector<int>> jobs) {
int answer = 0;
int t = 0; // 시간
int cnt = 0; // 완료한 작업의 수
int size = jobs.size();
int work = 0; // 현재 진행중인 작업의 작업량
pair<int,int> rq = {0,0}; // 작업중인 job의 상태 [작업량, 요청시간]
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 작업시간을 담은 pq
while (!(cnt == size)){
for (int i = 0; i < size; ++i){
if (jobs[i][0] == t)
pq.push(make_pair(jobs[i][1], jobs[i][0])); // 요청받으면 ready queue에 올라감, cmp 함수 따로 만들기 귀찮아서 위치를 바꿔서 pq에 넣음
}
// 완료된 작업 빼주기
if (rq.first != 0 && work == rq.first){
answer += (t - rq.second);
rq = {0,0};
work = 0;
++cnt;
}
// pq가 비어있지 않은데 rq가 비어있으면
if (!pq.empty() && rq.first == 0){
rq = pq.top(); // running queue에 pq에서 가장 작업시간이 짧은 친구를 데리고옴
pq.pop();
}
if (!rq.first == 0) { // 작업 진행
++work;
++t;
}
else
++t;
}
answer /= size;
return answer;
}
3. 후기
아는 문제여서 반가웠던 만큼, 약간은 방심하지 않았나 싶습니다. 이렇게 오래 걸릴 문제가 아니었는데 ㅠ
테스트케이스를 만들 때 더욱 더 자세하게 살펴봐야겠다는 생각이 들었습니다. 오류를 보다 정확하게 발견하기 위해서 만드는 건데 이걸 잘못 만들어버리면 의미가 없어지는데다가 오류를 찾기 더 힘들어지니까요!
출처 : 프로그래머스 고득점KIT, programmers.co.kr/learn/courses/30/lessons/42627
최근댓글