알면 도움되는 코딩 테스트 유형: 10) #Priority_Queue

우선순위 큐란?

 

• 우선순위 큐는 데이터들이 우선순위에 따라 처리되는 자료구조입니다. 각 요소는 우선순위 값과 함께 저장되며, 우선순위 값에 따라 요소들이 정렬됩니다. 일반적으로 작은 값이 높은 우선순위를 가지게 됩니다.
• 우선순위 큐를 사용하면 데이터를 삽입하거나 삭제할 때 항상 가장 우선순위가 높은(또는 낮은) 요소를 빠르게 접근할 수 있습니다. 이러한 특성으로 인해 다양한 문제에서 유용하게 활용됩니다.
• 일반적으로 파이썬에서는 heapq 모듈을 활용하여 간편하게 우선순위 큐를 구현할 수 있습니다. heapq 모듈은 최소 힙(min heap)의 형태로 구현되어 있으며, 최대 힙(max heap)을 구현하기 위해서는 값을 음수로 변환하여 활용하는 방법도 있습니다.

 

코딩 테스트에서의 우선순위 큐 문제 접근 방법

 

• 우선순위 큐 문제를 해결하기 위한 접근 방법은 다음과 같습니다.

 

1. 필요한 라이브러리/자료구조 선택: 파이썬에서는 heapq 모듈을 활용하여 간편하게 우선순위 큐를 구현할 수 있습니다. 다른 언어에서도 해당 언어의 기본 제공 라이브러리나 직접 구현할 수 있는 자료구조를 활용합니다.
2. 데이터 추가 및 삭제: 우선 순위 큐에 데이터를 추가하거나 삭제하는 연산을 수행합니다. 데이터 추가 시, 해당 데이터의 우선 순위 값을 기준으로 정렬됩니다.
3. 필요한 연산 수행: 문제의 요구사항에 맞추어 필요한 연산(예: 최솟값/최댓값 추출, 변경 등)을 수행합니다.
4. 결과 확인: 문제에서 요구하는 결과를 확인하기 위해 필요한 추가적인 작업을 수행합니다.

 

2075번: N번째 큰 수

 

  문제  

 

• N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

• 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

 

  해결 방법  

 

• 이 문제는 주어진 2차원 배열에서 N번째로 큰 값을 찾는 것이 목표입니다.

import heapq
import sys; input=sys.stdin.readline

n = int(input())
heap = []

for _ in range(n):
    nums = list(map(int, input().split()))
    if not heap:
        for num in nums:
            heapq.heappush(heap, num)
    else:
        for num in nums:
            if heap[0] < num:
                heapq.heappop(heap)
                heapq.heappush(heap, num)

while len(heap) > n: heapq.heappop(heap)

print(heap[0])

• 각 줄마다 숫자들을 읽어올 때마다 우선순위 큐에 추가하고, 만약 우선순위 큐의 사이즈가 N보다 커지면 가장 작은 값(우선순위 큐의 root 노드)을 제거합니다. 이렇게 하면 항상 우선순위 큐에는 입력된 숫자들 중에서 가장 큰 N개의 숫자만 남게 됩니다.
• 모든 숫자를 처리한 후에도 만약 우선순위 큐의 사이즈가 N보다 많으면 계속해서 가장 작은 값을 제거하고, 결국 남아있는 값 중에서 가장 작은 값이 바로 전체 입력 중에서 N번째로 큰 수가 됩니다.

 

 

1655번: 가운데를 말해요

 

  문제  

 

• 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
• 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

 

  해결 방법  

 

• 이 문제는 수열의 중간값을 찾는 문제로, 입력되는 숫자들을 하나씩 처리하면서 중간값을 구하는 방식으로 풀이합니다.

import heapq
import sys; input=sys.stdin.readline

n = int(input())
max_heap = []
min_heap = []

for _ in range(n):
    num = int(input())
    if len(max_heap) == len(min_heap):
        heapq.heappush(max_heap, -num)
    else:
        heapq.heappush(min_heap, num)

    if min_heap and max_heap[0] * -1 > min_heap[0]:  
        temp_max = heapq.heappop(max_heap) * -1
        temp_min = heapq.heappop(min_heap)
        
        heapq.heappush(max_heap, -temp_min)
        heapq.heappush(min_heap, temp_max)

    print(max_heap[0] * -1)

• 위 코드에서 maxheap과 minheap 두 개의 우선순위 큐를 사용합니다. maxheap은 입력된 숫자들 중에서 작거나 같은 값을 저장하며, minheap은 입력된 숫자들 중에서 큰 값을 저장합니다. 이렇게 하면 각각의 우선순위 큐에서 가장 위에 있는 값이 항상 현재까지 입력된 숫자들의 중간값이 됩니다.
• 각 숫자가 입력될 때마다 두 우선순위 큐를 조정하여 항상 maxheap의 최대값이 minheap의 최소값보다 작거나 같도록 유지하고, 그 결과를 출력합니다.

 

• 우선순위 큐 문제를 해결하기 위해서는 문제의 조건과 요구사항을 명확히 이해하고, 필요한 연산을 구현하는 것이 중요합니다. 문제에서 요구하는 결과를 얻기 위해 필요한 추가 작업이 있다면 그에 맞게 코드를 작성해야 합니다.