리버스 가희와 프로세스 : 상황 도식화를 잘 시켜 봅시다.

 가희배 코딩테스트 1회에서 나온 7번 문제는 가희와 프로세스 문제의 결과값이 주어졌을 때, 거꾸로 인풋 값을 만들어 보라는 문제였습니다. 항상 가능한 경우만 주었기 때문에 쉬울 거라고 생각했습니다. 그런데, 실제로 대회 때 문제를 푸신 분들은 그리 많지 않았고 골드 1로 평가되는 기염을 토하게 되었습니다. 사실 불가능한 경우까지 출력하라고 했는데, 진짜 그렇게 출제 했다면 100% 플레급으로 뛰었을 거라 생각합니다.

 

---

 그러면 무엇이 이렇게 어렵게 만들었을까요? 문제에서 설명하는 알고리즘을 단순화 하는 것이 제일 어렵지 않았나 싶습니다. 게다가 실행 결과를 가지고 가능한 입력값을 만들라고 하니 당황할 수 밖에 없었을 겁니다. 사실 제가 맞닥트렸어도 매우 당황했을 겁니다. 일단, 가희와 프로세스의 나온 입력 예제를 변형 시켜보면서 문제 상황을 이해하는 게 필수인 듯 싶어요.

 

 프로세스 id가 1인 것의 초기 우선 순위는 1, 2인 것의 우선 순위는 3, 3인 것은 4라고 해 보겠습니다. 이들이 실행을 마치는 데 필요한 시간은 5초로 동일하다 가정해 봅시다.

 

 

 그러면 먼저, 스케쥴러는 이러한 정보를 받을 겁니다. 기준에 따르면, 우선 순위가 가장 높은 것을 선택한다고 했으므로 3인 선택이 될 겁니다. 다음에, 알고리즘 대로라면 3을 제외하고 나머지 프로세스의 우선 순위가 하나 높아지는 것인데, 사실 3만 하나 낮아져도 됩니다. 나머지 프로세스의 기준으로 보았을 때, 3의 priority가 하나 낮아지거든요.

 

 

 그러면, id가 3인 프로세스의 priority 값이 3이 되었습니다. 그 다음에 어떤 것이 선택될까요? id가 2인 것이 선택될 겁니다. 왜? 우선 순위가 같은 게 2와 3이 있지만, id 값이 더 작은 건 2이기 때문입니다.

 

 

 그러면, 2가 선택되고, 2의 priority가 하나 감소하게 됩니다. 이 상태에서 다음에 스케쥴러는 어떤 것을 선택하게 되나요? id가 3인 것을 선택합니다. 왜냐하면 우선 순위가 제일 높기 때문입니다.

 

 

 다음에는 id가 2인 것이 선택됩니다. 왜요? p가 제일 높은 것이 id가 2인 것과 3인 것이 있는 상황인데요. 2가 3보다 작기 때문이에요.

 

 

 다음에는 어떨까요? 이제 id가 3인 것을 실행시킬 겁니다.

 

 

 그 다음에 어떻게 실행이 될까요? 1, 2, 3 순서대로 실행이 될 것은 매우 자명해 보입니다. 우리는 간단한 데이터를 넣어봄으로써, 아래와 같은 추가적인 사실을 관찰할 수 있었어요.

 

 

 위 그림은 id가 x(1), x(2), ... , x(i)인 프로세스가 있는 상황이에요. x(i) < x(i+1)이라고 해 보겠습니다. 모든 프로세스가 실행 시간이 남아 있다고 한다면, 실행 순서는 어떻게 될까요? x(1), x(2), ... , x(i)가 될 겁니다. 이 순서대로 스케쥴러가 1 사이클을 실행시킨다고 봐도 좋겠네요.

 

 

---

 우선 순위가 같은 모든 프로세스들을 id 순서대로 쭉 실행시키는 것을 1 사이클이라 보기로 했어요. 그러면, 상황을 아래와 같이 도식화를 시킬 수 있습니다. 실행 시간이 모두 5인 id가 1이고 우선 순위가 1인 프로세스, id가 2이고 우선 순위가 3인 프로세스, id가 3이고 우선 순위가 4인 프로세스가 있다 해 봅시다.

 

 

 먼저 3이 실행될 겁니다. 그 다음에 id가 3인 녀석의 priority가 3으로 감소하겠죠.

 

 

 다음에는 2, 3 순서로 돕니다. 왜냐하면 id가 2인 프로세스와 3인 프로세스의 우선 순위가 3으로 같기 때문입니다.

 

 

 그 다음에도 2와 3이 실행될 겁니다. 왜? 우선 순위가 2이기 때문입니다.

 

 

 그 다음에는 1, 2, 3 순서대로 실행되겠죠? 이런 식으로 상황 도식화를 하다 보면 이런 그림이 그려지게 됩니다.

 

 

 뭔가 구간으로 치환할 수 있을 거 같이 생겼는데요. 이 그림이 가희와 프로세스 2 문제를 풀기 위한 핵심 키였습니다. 그리고 포스팅에서 설명하고 있는 리버스 가희와 프로세스 문제를 푸는 데 도움이 되는 그림입니다.

 

 

---

 이제 저 그림을 바탕으로 어떻게 문제를 해결해야 할 지 간단하게 브리핑 해 봅시다. 2, 4, 1, 2 순으로 수행되었다 해 봅시다.

 

 그러면 처음에 id가 2인 것의 우선순위가 u였을 겁니다. 다음에 또 다시 2가 실행된다면 u-1이 되겠죠?

 

 

 이제 4와 1이 실행되었을 당시 우선 순위를 채워야 하는데요. 만약에 2가 처음에 실행되었을 당시에 4의 우선순위가 u보다 컸다면 2보다 4가 먼저 실행되었을 겁니다. 그런데 2가 먼저 나왔으니, 2가 처음에 실행되었을 당시, 4의 priority는 u보다는 작거나 같습니다. 다음에 1이 실행되었는데요. 1의 priority가 u-1보다 작았다면, 2, 4가 실행되고 나서 1이 올라가지 않았을 겁니다. 그러니, 위 그림과 같이 그려질 건데요.

 

 그런데 1 전에 4가 실행되었습니다. 그 이야기는 4가 실행되었을 당시에는 1보다는 우선 순위가 높았다는 것을 의미해요. 따라서 아래와 같이 그려질 겁니다.

 

 

 뭔가 증가하는 순열별로 끊은 거 같은데요. 사실 맞습니다. 왜 그러냐면 id가 더 높은 것이 낮은 것보다 먼저 실행되었다면 무조건 id가 높은 쪽의 priority가 높을 수 밖에 없거든요. 그러면 이런 경우는 어떨까요?

 

 

 2, 4, 1, 5 순으로 실행되었습니다. 그러면 4 > 1이니, 4를 기준으로 상황을 봅시다. 4가 실행될 당시 우선 순위가 u였다면, 2가 실행될 당시에는 priority가 u보다는 크거나 같아야 하고, 1과 5는 u보다 작거나 같아야 할 겁니다. 이 정보만 주어진 상태이니 이렇게 둬도 무방하다는 것을 알 수 있어요.

 

 

 핵심은 a < b일 때 b 다음에 a가 실행되는 경우에, b까지 1 사이클이 수행된다는 관찰을 하시면 됩니다. 1, 3, 7, 8, 11 순으로 실행되었다면 우선 순위가 같은 1, 3, 7, 8, 11이 큐에 있어도 되거든요. 이 관찰까지 하셨다면 구현을 하는 것은 3분이면 할 수 있습니다. 사실 우선 순위가 같으면 id 오름차순으로 실행된다는 조건이 핵심 키였습니다.

 

 여담이지만, 1회 때 내려던 문제 2개가 있었습니다. 이 두 문제가 반려된 대신에, 리버스 가희와 프로세스, 가희와 프로세스 2가 추가되었는데요. 가희의 수열놀이 시리즈만큼 매우 잘 뽑히지 않았나 싶습니다.