반응형

 안녕하세요. 팀 codingdog입니다. 1회에 출제된 문제 중 가장 어려웠던 문제는 가희와 프로세스 2 문제였는데요. 대회 당시에 단 2분만 푸셨을 정도로 쉽지 않은 문제였습니다. 어떤 점이 발목을 잡았는지, 그래서 어떻게 접근을 해야 했는지만 보겠습니다.


 먼저 기본 아이디어는 가희와 프로세스 1 문제와 동일합니다. 나머지 프로세스의 우선순위가 1 상승하는 것을 상대적인 관점에서 생각한다. 즉, 현재 실행되고 있는 프로세스가 실행되면, 우선순위가 1 하락한다. 달라보이지만, '상대적'인 관점에서 생각하면 똑같은 말입니다. 어렵지 않죠? 문제를 요래 변형하는 게 첫 번째 포인트입니다. 이 부분은 2회의 가희와 거북이 인형 문제에서도 교과서에 나온 개념 그대로 연계해서 출제한 적이 있습니다.

 

 예제 1번을 보면, 1번 프로세스와 2번 프로세스의 초기 우선 순위가 1이였습니다. 그리고 실행을 마치는 데 둘 다 5초가 필요했단 말이죠. 상황을 어떻게 도식화 시킬 수 있을까요?

 

 

 먼저 우선순위가 1인 상태에서 1과 2가 cycle 1을 돌아버립니다. 그러면 프로세스 1번과 2번의 우선순위는 각각 하나씩 감소하겠죠?

 

 

 다음에 우선 순위가 0인 상태에서 1과 2가 또 cycle 1을 돌아요. 마찬가지로 사이클이 다 돌면, 1번과 2번의 우선순위는 하나씩 감소하게 됩니다. 둘 다 총 5만큼의 시간이 필요하다 했으므로, 전체적인 프로세스가 실행되는 순서 그림을 그려보면 아래와 같이 됩니다.

 

 

 별로 어렵지 않죠? 이제 데이터만 살짝 바꿔 봅시다.

 

 


 프로세스 1의 실행 시간은 3초이고 초기 우선 순위가 2라고 합시다. 2의 실행 시간은 4초이고 초기 우선 순위가 1이라 할게요. 그러면 이건 어떻게 그릴 수 있겠나요?

 

 

 처음에 프로세스 1이 실행될 겁니다. 프로세스 2는 초기 우선 순위가 2이므로 실행되지 않아요. 그래서 첫 사이클이 돌 때에는 1만 돌게 됩니다.

 

 

 다음에, 1번 프로세스의 우선 순위가 1이 되었고, 2번 프로세스의 초기 순위가 1이므로, 사이클이 또 돌 때는 1번과 2번 프로세스 둘 다 실행되게 됩니다.

 

 

 다음에 둘 다 priority가 1 감소해서 0이 됩니다. 그 다음에는 어떻게 그려야 할까요?

 

 

 군청색으로 칠한 부분을 보면 되는데요. 프로세스 1의 초기 우선순위는 2라고 했어요. 맞나요? 그러면, 4번째 사이클 (-1이라고 쓰여져 있는 시점)에 1번이 돌 수 있나요? 아뇨. 그렇지 않습니다. 왜? 1번이 실행을 마치는 데 필요한 시간이 3초라고 했기 때문입니다. 그리고 2번 프로세스의 초기 우선 순위가 1인 상황이였죠. 실행을 마치는 데 필요 시간이 4초였는데요. 1, 0, -1, -2일 때 실행된다는 것을 그릴 수 있어요.

 

 이제 이것을 일반화 시켜 봅시다. process x의 초기 우선 순위가 p(x)이였다 해 볼게요. t(x)초 동안 실행이 된다 했을 때, process x에 대한 정보는 어떻게 그려질 수 있을까요?

 

 

 위와 같이 그릴 수 있습니다. 구간처럼 바뀌어 버립니다. 여기까지 도식화를 시켰다면 이미 푸셨다고 보시면 됩니다. 이 작업이 매우 까다로웠거든요.

 

 


 문제는 t초일 때 어떤 프로세스가 실행될까? 를 어떻게 빨리 찾느냐입니다. 제한 조건을 보면, 이 질문이 최대 50번 들어온다고 했으니, O(Qn)도 통과한다는 의미입니다. n이 10만까지, Q가 50까지 들어오기 때문입니다. t초일 때 어떤 프로세스가 실행될까? 이 질문은 매우 어렵습니다. 대신에, t초일 때 어떤 사이클이 돌아갈까? 혹은 t초일 때 올리는 프로세스의 우선 순위 값에 대한 질문은 상대적으로 쉽습니다. 예를 들어볼까요? 예제 1번에서 5초일 때 실행되는 프로세스는 1이에요. 이걸 어떻게 구할까요?

 

 

 우선순위 1일 때 실행되는 프로세스 수와 우선순위 0일 때 실행되는 프로세스 수를 합하면 4입니다. 이는 5보다 작습니다.

 

 

 그런데 여기에 우선순위가 -1일 때 실행되는 프로세스 수까지 합하면 6이 됩니다. 이 6은 5보다 같거나 큽니다. 따라서, 5초일 때 위 그림에서 cycle -1 이라고 표시된 사이클을 돈다는 것을 알 수 있어요. 그리고 cycle 1에 실행된 process 수와 cycle 0에 실행된 process 수를 합친 것이 4가 나왔어요. 그 말인 즉슨, 5초일 때에는 cycle -1일 때 1번째로 선택되는 친구가 실행된다는 의미에요.

 

 

 그런데 사이클 -1일 때에는 1과 2 둘 다 실행될 수 있습니다. 이 때 1과 2는 우선 순위가 -1인 상황이죠. 이 중 1번째로 실행되는 친구는 1입니다. 각 사이클마다 실행되는 프로세스의 수는 0개 이상이므로 이분 탐색을 적용할 수 있어요. 끝났네요.

 

 


 gahui(t)는 t초일 때 어떤 프로세스가 실행되는지 구하는 함수입니다. 사이클마다 0개 프로세스 이상이 실행되니 이분 탐색을 적용할 수 있다고 하였습니다. 그러니, 일반적인 이분 탐색 loop를 돌려줍니다. 그런데 변형한 문제를 생각해 봅시다. 우선 순위가 더 낮으면 더 많은 시간이 지난 것일까요? 우선 순위가 더 높아야 더 많은 시간이 지난 것일까요? 전자입니다.

 

 

 52번째 줄에서 f(mid)가 t보다 크거나 같다는 의미는, 우선 순위가 mid인 프로세스를 실행하였을 때, t초보다 크거나 같은 시간만큼 지났다는 의미입니다. 이것만 검사하면 될까요? 아닙니다. 우선 순위가 mid+1인 프로세스를 실행하였을 때, t초보다 크거나 같아지는 경우가 있는지를 검사해야죠. 이를 55번째 줄에서 수행합니다.

 

 55번째 줄 if문이 걸렸다는 의미는 t초가 지난 시점에, 우선순위가 mid인 어떤 프로세스를 실행했다는 의미입니다. 그 프로세스를 어떻게 구할까요? 실행 중에, 우선 순위가 mid가 될 수 있는 프로세스들만 좌르륵 모아서 보면 됩니다. 이 풀이는 Q가 커지면 적용할 수 없습니다. Q가 50이 된 이유는 당연하게도 모의 코딩 테스트에 내려고 했기 때문입니다. Q가 2000이였으면 이미 P중위는 가볍게 넘어갔을 겁니다. 그런데 3회에 그런 게.. RIP

 

 

 도식화를 시켰을 때 구간이 나왔기 때문에, 판단 함수는 요래 작성할 수 있습니다. 풀 소스 코드는 여기서 보실 수 있습니다.

반응형

댓글을 달아 주세요