자료구조 (1) - 우선순위 큐, 힙

---

문제 링크

문제

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 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보다 작거나 같은 양의 정수이다.

---

출력

첫째 줄에 최소 비교 횟수를 출력한다.

---

자료구조 선택

문제를 보면 작은 묶음의 카드부터 두 개씩 합치는 것이 최소한의 비교 횟수를 만들어낼 수 있다. 따라서 주어진 카드 묶음들을 오름차순으로 정렬하고, 작은 것부터 두 개씩 합쳐 나가는 것이 핵심이다.

이를 위해 우선순위 큐(힙)을 사용하면 효과적으로 문제를 해결할 수 있다. 힙에서 원소를 꺼낼 때마다 가장 작은 원소부터 꺼내진다.

우선순위 큐 (Priority Queue)

각 요소가 우선순위를 갖고 있으며, 가장 높은 (또는 낮은) 우선순위의 요소부터 먼저 처리되는 데이터 구조

✅ 구현 방법

1. 배열:
   • 모든 요소를 단순 배열에 넣고, 가장 높은 우선순위의 요소가 필요할 때마다 배열 전체를 탐색
2. 연결 리스트:
   • 데이터를 연결 리스트에 순차적으로 추가하고, 우선순위에 따라 요소를 찾을 때마다 전체 리스트를 탐색
3. 바이너리 힙 (일반적으로 사용됨):
   • 가장 흔히 사용되는 구현 방법으로, 트리 구조를 갖는 바이너리 힙을 사용하여 우선순위 큐를 구현

✅ 시간 복잡도

1️⃣ 배열

• 삽입: O(1)
• 삭제 (우선순위에 따른): O(n)

2️⃣ 연결리스트

• 삽입: O(1) (리스트의 끝에 추가하는 경우)
• 삭제 (우선순위에 따른): O(n)

3️⃣ 바이너리 힙

• 삽입: O(log n)
• 삭제 (우선순위에 따른): O(log n)

힙(Heap)

완전 이진 트리의 일종으로, 부모 노드와 자식 노드 간의 순서 관계만 유지되며, 레벨별로 저장되어 있음

1️⃣ 최소 힙

부모 노드는 자식 노드보다 항상 작거나 같아야 하며, 우선순위 큐에서 최소 값을 먼저 처리하려는 경우에 사용

2️⃣ 최대 힙

반대로 부모 노드가 자식 노드보다 크거나 같아야 하며, 최대 값을 먼저 처리하려는 경우에 사용

---

파이썬 우선순위 큐(힙) 구현

heapq는 Python의 표준 라이브러리 중 하나로, 힙 (heap) 자료구조의 기능을 제공

• 힙은 완전 이진 트리의 일종으로 우선순위 큐를 구현하는 데 사용됨
• heapq는 주로 최소 힙(min-heap)을 구현하는 데 사용되며, 따라서 힙의 최상단(root)에는 가장 작은 값이 위치하게 됨

---

heapq 주요 메서드

1. heapify(iterable)

   리스트를 즉시 힙의 형태로 변환

• 시간복잡도: O(N)

h = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(h)
print(h)  # 결과: [1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

---

2. heappush(heap, elem)

   힙에 원소를 추가

• 시간복잡도: O(log N)

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 3)
heapq.heappush(h, 7)
print(h)  # 결과: [3, 5, 7]

---

3. heappop(heap):

   힙에서 가장 작은 원소를 제거하고 그 값을 반환

• 이 연산은 O(log N)의 시간복잡도를 가집니다.

   h = [3, 5, 7]
   val = heapq.heappop(h)
   print(val)  # 결과: 3
   print(h)    # 결과: [5, 7]

---

4. heappushpop(heap, elem):

   힙에 원소를 넣은 후, 가장 작은 원소를 제거하고 그 값을 반환

h = [5, 7]
val = heapq.heappushpop(h, 6)
print(val)  # 결과: 5
print(h)    # 결과: [6, 7]

---

5. heapreplace(heap, elem):

   힙에서 가장 작은 원소를 제거하고, 새로운 원소를 추가

• heappop()을 호출한 후 heappush()를 호출하는 것보다 더 빠르다

---

풀이

import heapq

N = int(input())
cards = [int(input()) for _ in range(N)]

# 우선순위 큐로 변환
heapq.heapify(cards)

result = 0

while len(cards) > 1: # 카드 묶음이 하나 이상 남았을 때
    # 가장 작은 두 묶음 꺼내기
    sum_value = heapq.heappop(cards) + heapq.heappop(cards)
    result += sum_value
    heapq.heappush(cards, sum_value)

print(result)

---

어렵다