알고리즘 스터디 우선순위 큐-1715번
큐 알고리즘 1715번 풀이
study백준 정렬 1715번
안녕하세요. GDSC 웹 코어 멤버 송민선입니다.
먼저 문제 분석부터 진행해보겠습니다.
문제는
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 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개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.
문제 해석엔 큰 어려움이 없는 것 같네요. 작은 수 끼리 합치고 그 합친수를 다시 하나의 덩어리로 생각한 상태에서 계속 작은값 2개끼리 덧셈을 진행하는 문제입니다.
ex)
heap => [10, 20, 50]
total = 0
Step 1
10+20 = 30,
total = 30
heap => [30, 50]
Step 2
30+50 = 80
total = 30 + 80 = 110
heap => [80]
end
의 형태로 진행이 됩니다.
heap이란?
Heap은 최댓값 및 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조라고 보면 됩니다.
자식노드가 2개인 이진 트리형식으로 되어있으며 최소힙 기준으로 부모노드가 자식노드보다 작거나 같아야 합니다.
힙의 시간복잡도는 O(log n)이 소요됩니다.
힙은 기본적으로 배열형태의 자료구조입니다.
배열내에서 힙 부모 자식관계를 파악할려면
부모노드 => a[(i-1)//2]
왼쪽노드 => a[i*2 + 1]
오른쪽노드 => a[i*2 + 2]
와 같은 형태로 인덱싱을 접근할 수 있습니다.
다만 실전에서 heap을 사용해야 할 문제에서 적용할 수 있을지 ㅠㅠ 자신이 없네요.
heapq 활용
다행히 저희는 heap을 구현할 때 배열에 array의 index를 이리저리 주는 그런 짓은 안해도 됩니다.
파이썬 모듈중에 heapq라는게 있어 쉽게 heap자료구조를 다룰 수 있습니다.
# heapq 사용예시
import heapq
myheap = []
heapq.heappush(myheap, 3)
heapq.heappush(myheap, 5)
heapq.heappush(myheap, 2)
heapq.heappush(myheap, 1)
heapq.heappush(myheap, 0)
print("heap => ", myheap) #heap => [0, 1, 3, 5, 2]
print(heapq.heappop(myheap)) # 0
print(heapq.heappop(myheap)) # 1
print(heapq.heappop(myheap)) # 2
만약 heapq없이 array로 구현을 한다면 삽입, 삭제가 일어날때마다 array를 다시 정렬해줘야 합니다.
하지만 heapq를 사용함으로 인해 그러한 과정 없이 빠르게 heapq가 사용이 가능합니다.
heapq는 최소힙만 지원하기 때문에 최대힙을 사용하기 위해서는 값을 받을 때 마이너스를 곱해줘서 입력하는 방법이 있습니다.
이번 문제를 풀다보면 최대힙을 사용해야하는 경우가 있는데 모든값에 마이너스를 주고 다시 출력할 때 마이너스를 곱하면 최대값을 쉽게 구할 수 있습니다.
풀이방법
import sys
import heapq
num = int(sys.stdin.readline())
myheap = []
for _ in range(num):
number = int(sys.stdin.readline())
heapq.heappush(myheap, number)
count = len(myheap)
sum = 0
for i in range(count - 1):
if count == 1: # 카드가 한개이면 비교대상이 없으니 0을 출력한다.
sum += 0
else:
value_1 = heapq.heappop(myheap) # 최솟값
value_2 = heapq.heappop(myheap) # 그 다음 최솟값
total = value_1 + value_2
sum += total # 합치고
myheap.append(total) # 다시 넣기
print(sum)
마무리
처음에
10, 20, 30이 있으면
step1 => 10+20
step1 => 10+20+40
이렇게 진행하는줄 알고 접근했는데 생각해보니 앞에 합산한게 카드내에서 가장 큰값이면 이 경우가 만족하지 않기 때문에 적용이 안됩니다.
힙에 대해 이해하고 있으면 빠르게 풀 수 있는 문제였습니다. 물론 저는 오래걸렸습니다 ㅎㅎ
