우선순위 큐 (Priority Queue) 알고리즘 정리

Heap을 사용하여 우선순위 큐 알고리즘을 공부해봅시다~~~✏️

 

1️⃣ 기본 : heapq를 사용하면 Minheap이 디폴트이다!

                   heap에서 코드로 구현했던 루트노드의 값을 출력하고,

                   맨 마지막에 있는 값을 최상단으로 올려 정렬하는 과정은 heappop()을 활용한다.

import heapq

arr = []

# insert, Minheap이 디폴트
heapq.heappush(arr, 4)
heapq.heappush(arr, 1)
heapq.heappush(arr, 3)
heapq.heappush(arr, 9)
heapq.heappush(arr, 6) # 1 4 3 9 6

# heapq.heappop(arr) -> top() and pop()
print(heapq.heappop(arr)) # 1
print(heapq.heappop(arr)) # 3

2️⃣ 우선순위를 부여해보자

import heapq

arr = []

# 튜플을 이용해서 우선순위도 정해줄 수 있음
heapq.heappush(arr, (1, 'banana'))
heapq.heappush(arr, (5, 'apple'))
heapq.heappush(arr, (3, 'mango'))
heapq.heappush(arr, (2, 'melon'))
heapq.heappush(arr, (4, 'peach'))

# 1번 원소 출력
print(heapq.heappop(arr)[1]) # banana
print(heapq.heappop(arr)[1]) # melon
print(heapq.heappop(arr)[1]) # mango
print(heapq.heappop(arr)[1]) # peach
print(heapq.heappop(arr)[1]) # apple

3️⃣ heapify() : 일반 리스트를 힙 자료형으로 만들어 줌, 역시 기본값은 Minheap

import heapq

arr = [2,5,3,1,5]

# 힙의 자료형으로 한 번에 바꿔줌
heapq.heapify(arr) # 힙의 자료형이니까 루트노드의 값은 가장 작은 값, 나머지는 모름

for _ in range(len(arr)):
    print(heapq.heappop(arr))

4️⃣ Maxheap을 만들어 보자

4️⃣-1️⃣ 튜플 활용

arr = []

# 튜플의 우선순위 사용
heapq.heappush(arr, (-5, 5))
heapq.heappush(arr, (-2, 2))
heapq.heappush(arr, (-4, 4))
heapq.heappush(arr, (-3, 3))
heapq.heappush(arr, (-1, 1))

for _ in range(len(arr)):
    print(heapq.heappop(arr)[1])

4️⃣-2️⃣ 음수(-) 활용

arr = []

heapq.heappush(arr, -1)
heapq.heappush(arr, -5)
heapq.heappush(arr, -2)
heapq.heappush(arr, -3)
heapq.heappush(arr, -4)

for _ in range(len(arr)): # 가장 먼저 나오는 수에 -를 붙여 양수 형태로 출력
    print(-heapq.heappop(arr))

 

✏️ 연습

1️⃣ 이중 for문 사용

maxheap = []
for i in range(len(arr)):
    heapq.heappush(maxheap, (-arr[i], arr[i])) # 우선순위가 제일 작은 것부터 출력

for i in range(len(arr)):
    print(heapq.heappop(maxheap)[1])

2️⃣ 람다 활용

rev = lambda x: x * -1
maxheap = list(map(rev, arr)) # arr 값에 음수 붙여서 maxheap 리스트 만들고
heapq.heapify(maxheap) # heap 자료형으로 만들고

for _ in range(len(arr)):
    print(-heapq.heappop(maxheap))

3️⃣ 관련 문제 풀이

각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다.
예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.
N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.
입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다.
숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.
출력 첫째 줄에 최소 비교 횟수를 출력한다.

입력
4
50
20
70
30
출력
320

입력
3
10
20
40
출력
100

 

내 코드

import heapq

cnt = 0
sums = 0
n = int(input())
arr = [int(input()) for _ in range(n)]
heapq.heapify(arr) # minheap으로 만들어 주기

for i in range(n):
    if i > 1:
        cnt += sums # 최초의 2번을 넘어가면 cnt에 sums더해주기
    num = heapq.heappop(arr)
    cnt += num
    sums += num

print(cnt)

다른 풀이

import heapq

n=int(input())  # 카드 개수 입력
card=[]

for i in range(n):
    heapq.heappush(card,int(input()))  #입력받은 카드 insert 해주기

answer=0
while len(card)>1:  # 카드묶음의 개수가 1개가 될떄까지 반복수행
    temp1=heapq.heappop(card) # 가장 작은 카드 묶음 빼오고
    temp2=heapq.heappop(card) # 그다음 작은 카드 묶음 뺴오고
    answer+=(temp1+temp2) # 두개를 합한것이 비교 횟수므로.. 총 비교횟수를 구하는 answer 변수에 더해주기
    heapq.heappush(card,temp1+temp2) #다시 한 묶음이 된 카드를 push 해주기
print(answer)