priority queue를 배웠으니, 응용 문제들을 풀어보면서 스킬들을 익혀 봅시다. 이 글에서는 파이썬을 이용해서, 기본 문제인 백준 가희와 프로세스 1 문제를 풀어보도록 하겠습니다.
- 우선순위 큐 자료구조를 알아봅시다. [링크]
문제 읽어보기
먼저, 제가 출제한 문제를 천천히 읽어봅시다. 이 문제를 요약하면 아래와 같음을 알 수 있어요.
- 1초마다 프로세스를 선택합니다.
- 프로세스는 우선 순위가 가장 높은 것
- 여러 개라면 id가 작은 것.
- 1초가 지나고 나면
- 선택된 프로세스는 실행을 마치는 데 필요한 시간 1 감소.
- 나머지 프로세스들의 우선 순위는 모두 1 증가
문제를 보니, 가장 ~한 것을 매 초마다 선택하는 것입니다. 가장 ~한 것과 우선순위 큐는 잘 어울리는 구조입니다. 따라서, 이 문제 또한 heap을 이용하는 문제임을 알 수 있습니다. 문제의 상황을 그대로 따라가 봅시다.
우선 순위가 0초일 때 -1, 3, 2, 5 였던 프로세스가 4개 있었다고 해 보겠습니다.
그러면, 우선순위가 5인 프로세스가 실행될 겁니다. 다음에 1초일 때, 실행되지 않은 나머지 프로세스들의 우선 순위가 1 증가할 겁니다. 이렇게 되면, pq를 사용할 이유가 없습니다. 오히려, 매 시간마다 n개의 프로세스들에 대해 우선 순위를 검사하면서 선택하는 것이 훨씬 빠를 겁니다.
그런데, 상대적인 관점에서 봅시다.
- 실행되지 않은 프로세스들의 우선순위를 1 증가시키는 것
- 실행된 프로세스의 우선순위를 1 감소시키는 것.
이 둘의 상황은 같은가요? 다른가요? 위 그림의 경우 1초일 때 1번 프로세스보다 4번 프로세스의 우선 순위가 5 높았습니다.
이 상황도 마찬가지입니다. 따라서, 문제의 상황과 실행시킨 프로세스의 우선 순위를 1 낮추는 상황은 같다고 할 수 있어요. 따라서 아래와 같은 로직을 구현하면 됩니다.
- 매 초마다 for loop를 돌면서 프로세스를 선택합니다..
- 선택한 프로세스를 실행 시킨 후에 남은 실행 시간이 0이면 pq에 넣지 않습니다.
- 그렇지 않으면 우선 순위를 1 감소시킨 후에 pq에 다시 넣습니다.
tuple 사용하기
이 문제는 다중 판단 기준이 있어요.
- 우선 순위가 높은 순
- 우선 순위가 같다면 id가 작은 순
이 경우 무엇을 이용해야 하는가? tuple을 이용하면 편해요. 우선순위랑 id 모두 int로 주어졌고, int는 비교 가능합니다. 그리고, (int, int) 또한 비교 가능합니다. tuple도 __lt__와 같은 비교가 구현되어 있습니다. 고로, 이를 pq에 집어넣어서 비교하면 됩니다. 아래 예제를 봅시다.
1번 프로그램을 봅시다. 데이터 (1, 2), (-1, 3), (-1, 2) 이렇게 3개를 넣습니다. 그리고, 3회에 걸쳐서 heap에 있는 원소를 뽑습니다. 결과가 어떻게 나올까요?
(-1, 2), (-1, 3), (1, 2) 순으로 나옵니다. 왜? 먼저, (-1, 2)와 (-1, 3)은 (1, 2)보다 1번째 원소의 값이 작습니다. 따라서 우선순위가 더 높은 상황입니다. (-1, 2)와 (-1, 3)의 경우, 1번째 원소의 값은 같지만 2번째 원소가 다릅니다. 2가 3보다 작으므로 (-1, 2)가 제일 높아요.
즉, (int, int) 튜플에서는 아래와 같은 사실이 성립합니다.
- 1번째 원소가 작은 것이 우선순위가 높습니다.
- 1번째 원소가 같으면 2번째 원소가 작은 것이 우선순위가 더 높습니다.
그런데, 제가 출제한 백준 가희와 프로세스 1 문제는 상황이 다소 다릅니다.
- 우선순위가 높은 것
- 우선순위가 같으면 id가 작은 것
1번째 기준이 작은 것이 아니라 큰 것입니다. 이건 어떻게 해야 할까요?
1번째 기준에 대해서 -1을 곱해서 넣으면 됩니다. 위 그림을 봅시다.
- 우선순위가 -1이고 id가 4인 프로세스 1
- 우선순위가 3이고 id가 7인 프로세스 2
이 2개가 있어요. (-1, 4)와 (3, 7)을 pq에 넣으면 당연하게도 (-1, 4)가 먼저 빠질 겁니다. 그런데, 문제에서는 우선순위가 높은 것이 먼저 실행된다고 했어요. 그렇다면 우선순위 값에 -1을 곱해서 넣으면 됩니다. 아래 사실을 생각해 보면 됩니다.
- a > b이면 -a < -b이다.
통과 코드 보기
위 단락에서 아래 2가지를 배웠습니다.
- 비교 기준이 여러 개면, tuple을 사용하면 편하다.
- 정수의 경우 큰 것이 우선순위가 높게 하려면 -1을 곱해서 넣으면 된다.
물론, 이 방법이 통하지 않는 경우 __lt__를 오버라이딩 하면 됩니다. 해당 문제는 그렇지 않으니 tuple을 쓰시면 편합니다.
먼저, 프로세스 데이터를 넣는 것을 볼게요. prio는 높은 것이, idx는 작은 것이 우선순위가 높다고 했어요. -prio를 넣는 이유는 튜플을 우선순위 큐에 넣었을 때 값이 작은 것이 먼저 빠지기 때문이에요. 우선순위 바꿀 때, 정수의 경우 -1 곱하는 스킬은 생각보다 유용하니 알아두시면 좋습니다.
다음에, 매 초마다 우선순위가 높은 것을 뽑습니다. 프로세스에 대한 데이터가 나오는데, 남은 실행 시간과 우선순위, id 등이 나옵니다. time이 0이 아닌 경우에는, 업데이트 된 프로세스 정보를 다시 넣습니다. 여기서 중요한 것은 prio에 1을 더한다는 점인데요.
실행시킨 프로세스의 우선순위가 매 초마다 1 감소한다고 했어요. 그런데, 부호를 바꿨어요. 부호를 바꾼 상태에서는 연산의 방향도 바뀌게 됩니다. 이들을 적용한 코드는 링크를 보시면 됩니다.