[알고리즘] 우선순위 큐(Priority Queue) (feat. 백준 1715 카드 정렬하기)
Queue와 Priory Queue
일반적으로 알고있는 큐(queue)는 LIFO(Last In First Out)구조를 갖는 stack과 달리 FIFO(First In First Out)구조를 갖고 있어, 먼저 들어간 아이가 먼저 나오는! 그런 데이터 순서를 갖고 있다.
우선순위 큐(Priority Queue) 는 들어간 순서와는 상관없이 각 요소에 우선순위를 할당하고, 우선순위가 높은 데이터가 먼저 나온다.
자바스크립트의 경우에는 파이썬과 달리 우선순위 큐의 구현이 내장되어있지 않기 때문에 힙(heap) 이라는 자료구조 개념을 갖고, 직접 코드를 통해 구현해야한다.
그렇다면 힙(Heap)을 통해 우선순위 큐를 구현하기 전에 힙에 대해서 알아보자!
힙(Heap)이란 완전 이진 트리 구조를 갖는 자료 구조 이다. 마지막 레벨을 제외하고, 부모 노드는 무조건 두 개의 자식 노드를 가지며, 마지막 레벨의 모든 요소는 왼쪽부터 채워진다.
또한, 부모는 자식 요소보다 우선순위가 무조건 높다. 하지만 두 개의 자식 노드 중에서 어떤 자식의 우선순위가 높은지는 알 수 없다.
이러한 힙의 특징을 이용해 요소에 우선순위를 부여할 수 있다.
우선순위에 따라 값을 배치하는 위치가 달라지게 되는데 이 위치에 따라 '최소 힙'과 '최대 힙'의 유형으로 나뉜다.
[최소 힙]: 값이 가장 낮은 요소가 힙의 루트에 위치한다. 그렇기 때문에 최소값을 찾는데 유리하다. ( 자식요소 > 부모요소 )
[최대 힙]: 값이 가장 높은 요소가 힙의 루트에 위치한다. 그렇기 때문에 최댓값을 찾는데 유리하다. ( 자식요소 < 부모요소 )
이러한 이진 힙의 개념을 이용해 다익스트라 같은 최단 경로 알고리즘, 일부 그리디 알고리즘, 우선순위를 지정하는 알고리즘 등의 구현에 사용이 된다.
힙(Heap)을 이용해 우선순위 큐를 구현해보자!
본격적으로 우선순위 큐를 구현하기 전에 알아야 할 몇 가지 사항이 있다.
- 루트는 가장 위에 존재한다.
- 자식 노드를 기준으로 부모노드의 인덱스는 { Math.floor(( 자식 노드의 인덱스 - 1 ) / 2) }
- 부모 노드를 기준으로 왼쪽 자식은 { 부모노드의 인덱스 * 2 + 1 }, 오른쪽 자식은 { 부모노드의 인덱스 * 2 + 2 }의 인덱스를 갖는다.
힙을 구현은 "swap", "push", "pop" 등의 과정을 각각 분리하여 메서드를 정의하게 된다. 어떤 식으로 과정을 나누는 것 인지는 사바사 인 것 같다. 어쨌든 구현하려는 우선 순위 큐의 기능들을 잘 캡슐화하고, 읽기 쉬운 코드를 작성할 수 있도록 class 객체를 사용하는 것이 일반적인 것 같다. 함수로도 구현해보고, class 객체로도 구현을 해봤는데 확실히 class 객체로 구현하는 것이 코드 내에서 우선순위 큐의 코드만을 잘 묶어 정리가 잘 된 느낌이었다.
- swap
- push
- pop
내가 이번에 우선순위 큐를 구현하게 된 계기는 백준의 1715번 문제 [카드 정렬하기] 문제를 풀면서이다.
해당 문제에 대한 나의 답지를 분석해보며 각각의 메서드에 대해 자세하게 보자.
( 참고로 이 문제는 최소 힙을 구현하는 문제임 ! )
1. swap: 부모와 자식의 값을 바꾼다.
a와 b의 인덱스를 입력으로 받으면, 힙에서 두 개의 위치를 바꾼다.
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
2. push: 힙에 값을 삽입한다.
현재 노드와, 이 노드의 부모 노드의 인덱스를 구해 값을 비교한다.
만약 내 노드보다 부모 노드가 더 크면 그 두 요소를 바꾼다.
push(val) {
const { heap } = this;
heap.push(val);
let idx = heap.length - 1;
let parent = Math.floor((idx - 1) / 2);
while (idx > 0 && heap[idx] < heap[parent]) {
this.swap(idx, parent);
idx = parent;
parent = Math.floor((idx - 1) / 2);
}
}
3. pop: 루트에 존재하는 최소값(또는 최댓값)을 추출한다.
루트를 추출하고, 힙을 재구성한다.
- 만약 왼쪽에 자식이 있는데, 왼쪽 자식 요소가 부모보다 더 작으면 부모와 swap
- 오른쪽에 자식이 있는데, 오른쪽 자식 요소가 부모보다 더 작다면 부모와 swap
- 자식과 부모 모두 올바르게 위치한다면, 힙이 완전히 재구성된 것이므로 종료!
pop() {
const { heap } = this;
if (heap.length === 1) {
return heap.pop();
}
const result = heap[0];
heap[0] = heap.pop();
let idx = 0;
while (true) {
let left = idx * 2 + 1;
let right = idx * 2 + 2;
let next = idx;
if (left >= heap.length) break;
if (heap[left] < heap[next]) {
next = left;
}
if (right < heap.length && heap[right] < heap[next]) {
next = right;
}
if (idx === next) break;
this.swap(idx, next);
idx = next;
}
return result;
}
하나하나의 메서드를 하나의 코드에 옮겨담으면 아래와 같다.
let readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let input = [];
rl.on("line", (line) => input.push(line)).on("close", () => {
let [n, ...inputs] = input;
inputs = inputs.map(Number);
n = Number(n);
class MinHeap {
constructor() {
this.heap = [];
}
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
size() {
return this.heap.legnth - 1;
}
push(val) {
const { heap } = this;
heap.push(val);
let curIdx = this.size();
let parentIdx = Math.floor((curIdx - 1) / 2);
// 부모 노드와 자식 노드를 비교하여 자식 노드가 더 작다면 swap!
while (curIdx > 0 && heap[curIdx] < heap[parentIdx]) {
this.swap(curIdx, parentIdx);
curIdx = parentIdx;
parentIdx = Math.floor((curIdx - 1) / 2);
}
}
pop() {
const { heap } = this;
if (this.size() === 1) {
return heap.pop();
}
// 1. 최소값(루트)을 추출
const result = heap[0];
// 2. 힙에서 마지막 원소를 루트로 이동
heap[0] = heap.pop();
// 3. 현재 부모 노드를 0번 인덱스로 설정
let idx = 0;
// 힙 재구성
while (true) {
let left = idx * 2 + 1;
let right = idx * 2 + 2;
let next = idx; // 최소값을 부모 노드를 현재 인덱스로 설정
// 왼쪽에 자식이 있고, 부모보다 작다면 왼쪽 자식이 더 작으므로 'next'를 왼쪽 자식 인덱스로 설정
if (left < heap.length && heap[left] < heap[next]) {
next = left;
}
if (right < heap.length && heap[right] < heap[next]) {
next = right;
}
// 'next' 가 부모노드인 idx와 같다면, 힙이 재구성된 것이므로 종료
if (idx === next) break;
this.swap(idx, next);
idx = next; // 인덱스를 자식 노드로 이동
}
return result;
}
}
function sol(inputs) {
const minHeap = new MinHeap();
for (let i = 0; i < inputs.length; i++) {
minHeap.push(inputs[i]);
}
let answer = 0;
while (minHeap.heap.length > 1) {
let first = minHeap.pop();
let second = minHeap.pop();
let result = first + second;
answer += result;
minHeap.push(result);
}
console.log(answer);
}
sol(inputs);
});
📚 참고자료