[Coding Test] 가희와 프로세스1 (BAEKJOON: 21773번)

가희와 프로세스

가희와 함께하는 1회 코딩 테스트의 3번 출제문제입니다. 우선순위 큐를 이용해 푸는 문제였습니다.

이 문제를 풀며 배운 점은 다음과 같이 두 가지 입니다.

• 파이썬에서 우선순위 큐 적용법
• 파이썬에서 우선순위 큐의 비교 연산 조작법

먼저 Class를 이용해 푸는 방법입니다. 프로세스라는 클래스를 선언하고 그 내부에 비교 연산자를 오버라이딩합니다.

class Process:
    def __init__(self, p_id, p_time, p_prior):
        self.p_id = p_id
        self.p_time = p_time
        self.p_prior = p_prior

    def __lt__(self, other):
        if self.p_prior == other.p_prior:
            # 앞으로 오게 하고 싶은 것
            return self.p_id < other.p_id
        else:
            # 앞으로 오게하고 싶은 것
            return self.p_prior > other.p_prior

이는 다음과 같은 성질을 나타낸 것입니다.

• 우선순위가 같으면 p_id 기준 오름차순으로 정렬 (작은 것이 앞으로)
• 우선순위가 다를 때는 우선순위 기준 내림차순 정렬 (큰 것이 앞으로)

이렇게 나타낸 것입니다. C++에서 compare() 함수를 직접 작성해보신 분들은 쉽게 감을 잡으실 것 같습니다.

이를 List에 담은 뒤, heapq 모듈의 heapify(HEAP)를 이용해 힙 구조로 나타냅니다. 그리고 heappush(HEAP, item)와 heappop(HEAP)를 이용해 원소를 삽입 및 삭제합니다.

문제에서 시간이 지나면 큐에 존재하는 모든 프로세스의 우선순위를 높여주는 Aging을 적용하고 있습니다. 이는 운영체제에서 우선순위 기준 CPU 스케줄링 과정에서 기아(Starvation) 현상을 막아주는 기법입니다.

우선순위는 상대적인 것이므로 현재 바깥에 나와있는 프로세스의 우선순위를 하나 깎으면 큐 내부의 모든 원소에 접근할 필요가 없이 기아 현상을 예방할 수 있습니다. 이 과정을 코드로 표현하면 아래와 같습니다.

from heapq import heapify, heappush, heappop

class Process:
    def __init__(self, p_id, p_time, p_prior):
        self.p_id = p_id
        self.p_time = p_time
        self.p_prior = p_prior

    def __repr__(self):
        return 'p_id: {}, p_time: {}, p_priority: {}'.format(self.p_id, self.p_time, self.p_prior)

    def __lt__(self, other):
        if self.p_prior == other.p_prior:
            # 앞으로 오게 하고 싶은 것
            return self.p_id < other.p_id
        else:
            # 앞으로 오게하고 싶은 것
            return self.p_prior > other.p_prior


if __name__=="__main__":
    HEAP = []

    T, n = map(int, input().split(' '))
    for i in range(n):
        a, b, c = map(int, input().split(' '))

        # append Process instance to HEAP
        HEAP.append(Process(a, b, c))

    heapify(HEAP)

    t = 1
    while t <= T and HEAP:
        process = heappop(HEAP)

        # print current process p_id
        print(process.p_id)

        # execute 1 work
        process.p_time -= 1

        if process.p_time == 0:
            t += 1
            continue

        # change priority
        process.p_prior -= 1

        heappush(HEAP, process)
        t += 1

이는 클래스를 이용해 푸는 방법입니다. 나중에 조건이 복잡해지면 조금 더 유용하게 쓰일 것 같습니다. 더욱 간단한 방법은 다음과 같습니다.

• 정렬을 적용할 순서로 튜플을 만듭니다.
• 오름차순이면 그대로, 내림차순이면 minus 부호를 붙입니다.

이를 코드로 확인하겠습니다.

    for i in range(n):
        p_id, p_time, p_pri = map(int, input().split(' '))

        # append Process instance to HEAP
        HEAP.append([-p_pri, p_id, p_time])

    heapify(HEAP)

우선순위를 가장 먼저 확인하며 이는 내림차순으로 정렬되기에 앞에 minus 부호를 붙여줍니다. 둘이 같으면 다음으로는 p_id를 비교하므로 다음 원소에 p_id를 넣어줍니다. 끝으로 해당 리스트를 heapify를 통해 힙 구조화합니다.

추후에 우선순위 큐를 이용하는 문제가 등장하는 경우가 많을 것 같습니다. 다익스트라 알고리즘에서 우선순위 큐에 후보 노드들을 저장하는데, 이 기법을 활용해보시면 좋을 것 같습니다.