류나의 작은 DB

27살 류나의 바르고 다르게 살기

Programming/Algorithms in C++

우선순위 큐, 힙과 이진 탐색 트리

Ryuna (류준범) 2022. 4. 13. 20:50

이번 글에서는 우선순위 큐에 대해 알아봅니다. 이를 구현할 수 있는 두 가지 방법인 힙과 이진 탐색 트리에 대해서도 살펴봅니다.

목차

1. 우선순위 큐, 힙과 이진 탐색 트리

- 우선순위 큐란

- 힙이란

- 이진 탐색 트리란

2. 우선순위 큐의 구현

- 우선순위 큐의 두 가지 구현

- STL의 priority_queue와 multiset

3. 문제풀이: 힙과 이진 탐색 트리

- BOJ 11279번: 최대 힙 (실버 II)

- BOJ 1927번: 최소 힙 (실버 II)

- BOJ 11286번: 절대값 힙 (실버 I)

- BOJ 5639번: 이진 검색 트리 (골드 V)

4. 문제풀이: 우선순위 큐

- BOJ 7662번: 이중 우선순위 큐 (골드 IV)

- BOJ 2075번: N번째 큰 수 (실버 I)

- BOJ 11000번: 강의실 배정 (골드 V)

- BOJ 1715번: 카드 정렬하기 (골드 IV)

참고한 자료

C++ 자료구조론, Horowitz 외

http://www.yes24.com/Product/Goods/2656393

 

C++ 자료구조론 (2판) - YES24

C++ 언어의 최신 기능을 포함하도록 개정되었다. 예외와 템플릿과 같은 기능들은 제한적이긴 하지만 STL에 사용함으로써 내용전반에 걸쳐 포함되어 있다. 본서는 안전 해싱 알고리즘, 가중치 편

www.yes24.com

알고리즘 문제 해결 전략, 구종만

https://book.algospot.com/

 

알고리즘 문제 해결 전략

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트, ISBN 978-89-6626-054-6 새 소식 책 소개 <알고리즘 문제 해결 전략>은 새로운 알고리즘 책입니다. 종이에 적힌 의사코드

book.algospot.com

알고리즘 트레이닝: 프로그래밍 대회 입문 가이드, 안티 라크소넨

http://www.yes24.com/Product/Goods/108202966

 

알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드 - YES24

실전 알고리즘 공부법! 민간전승되던 고급 기법에서 최신 트렌드까지『알고리즘 트레이닝 2판』은 오늘날의 경진 프로그래밍에 관해 종합적으로 설명하고 있는 책이다. 저자는 경진 프로그래

www.yes24.com


우선순위 큐, 힙과 이진 탐색 트리

우선순위 큐란

우선순위 큐(priority queue)는 최대 또는 최소 원소를 탐색하거나 삭제할 수 있고, 임의의 원소를 삽입할 수 있는 자료구조입니다.

 

앞선 게시물에서 트리를 공부하면서 특정 조건을 지키도록 구성된 트리들은 탐색형 자료 구조로도 유용하게 쓰일 수 있다고 하였습니다. 우선순위 큐의 구현에는 특별한 형태의 이진 트리가 사용됩니다. 바로 힙과 이진 탐색 트리입니다.

힙이란

최대 힙(max heap)은 각 노드의 키 값이 자식 노드의 키 값보다 작지 않은 완전 이진 트리입니다. 최소 힙(min heap)도 이와 반대로 정의할 수 있습니다. 이 정의에 따라 최대 힙의 루트는 전체 트리에서 가장 큰 키 값을 가집니다. 또 힙은 완전 이진 트리이므로, 배열로 표현할 수 있습니다.

최대 힙에서의 삽입

최대 힙에서의 삽입 연산의 관건은 새 원소의 정확한 위치를 결정하는 것입니다. 이를 위해서는 완전 이진 트리에 노드 하나를 추가하고, 부모보다 자신이 클 경우 부모와 위치를 맞바꾸는 방식으로 올라가면 되겠죠.

최대 힙에서의 삭제

최대 힙에서의 삭제 연산의 경우 최대 원소(즉, 루트)를 삭제하게 됩니다. 그러면 비어버리는 루트를 무엇으로 채울까요? 완전 이진 트리의 마지막 원소를 삭제하고 거기 있던 값을 루트에 넣으면 될 것 같습니다. 그리고 자식보다 자신이 작을 경우 두 자식 중 더 큰 것과 맞바꾸는 것을 반복합니다.

이진 탐색 트리란

이진 탐색 트리(binary search tree)는 다음 성질을 만족시키는 이진 트리입니다.

1. 왼쪽 서브트리에 있는 키들은 그 루트의 키보다 작다.

2. 오른쪽 서브트리에 있는 키들은 그 루트의 키보다 크다.

3. 왼쪽, 오른쪽 서브트리도 모두 이진 탐색 트리이다.

순회와 탐색

이진 탐색 트리를 중위 순회하면 크기 순서로 정렬된 키의 목록을 얻을 수 있습니다. 또, 탐색은 이분 탐색과 비슷한 속도로 가능합니다.

삽입과 삭제

이진 탐색 트리에서의 삽입은 비교적 간단한데, 새 원소가 들어갈 위치를 이분 탐색과 유사한 방식으로 찾은 뒤 새 리프 노드로 추가하면 됩니다. 삭제의 경우, 리프 노드나 자식이 하나인 노드는 간단하고 자식이 둘인 노드도 어렵지 않습니다. 삭제하려는 원소를 왼쪽 서브트리에서 가장 큰 원소 또는 오른쪽 서브트리에서 가장 작은 원소로 대체하면, 대체한 원소는 원래 자식이 0 또는 1개임은 명백하므로 삭제 과정이 쉽습니다.

균형 잡힌 이진 탐색 트리

이진 탐색 트리가 만들어지는 방법(원소가 추가되는 순서)에 따라 노드가 한쪽으로 치우쳐 연결 리스트나 다름없게 되는 상황이 발생할 수 있습니다. 이 경우 연산이 그다지 효율적이지 못하게 되는데, 이를 방지하기 위해 여러 가지 '균형 잡힌 이진 탐색 트리(balanced binary search tree)'의 형태가 알려져 있습니다.

우선순위 큐의 구현

우선순위 큐의 두 가지 구현

우선순위 큐는 최대 또는 최소 원소를 쉽게 찾을 수 있도록 구현되어야 하므로, 힙이나 이진 탐색 트리를 이용하는 것이 효율적입니다. (균형 잡힌) 이진 탐색 트리는 최대 또는 최소 원소를 찾는 것이 \(O(\log n)\) 시간만큼 걸리는 반면 힙에서는 최대 또는 최소 원소가 반드시 루트에 있으므로 \(O(1)\)이죠. 따라서 힙이 우선순위 큐 구현에 더 적합한 것처럼 보입니다.

STL의 priority_queue와 multiset

우선순위 큐는 C++에서 priority_queue라는 구현체가 있습니다. 내부적으로는 힙을 이용하며 최대 또는 최소 원소를 빠르게 구할 수 있습니다.

priority_queue<int> q; // max heap 기반
priority_queue<int, vector<int>, greater<int>> q2; // min heap 기반

한편 multiset은 같은 값을 여러 개 가질 수 있는 집합 자료구조인데, 균형 잡힌 이진 탐색 트리를 기반으로 만들어져 있으며 우선순위 큐의 연산을 모두 지원하기 때문에 우선순위 큐처럼 쓸 수 있습니다. 하지만 실험에 의하면 속도가 다섯 배 정도 느립니다.

문제풀이: 힙과 이진 탐색 트리

BOJ 11279번: 최대 힙 (실버 II)

https://www.acmicpc.net/problem/11279

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

최대 힙을 만들어보는 문제입니다. 물론 STL의 자료구조를 컨테이너를 사용해도 될 듯하지만 연습삼아 구현해 보았습니다.

#include <iostream>
#include <vector>
using namespace std;

#define ll long long

void I(vector<ll>& maxheap, ll x) {
	maxheap.push_back(x); // insert at end position
	int idx = maxheap.size() - 1;
	while (idx > 0 && maxheap[(idx - 1) / 2] < maxheap[idx]) {
		// if parent is smaller, swap and move to the parent
		swap(maxheap[idx], maxheap[(idx - 1) / 2]);
		idx = (idx - 1) / 2;
	}
}

void D(vector<ll>& maxheap) {
	if (maxheap.empty()) {
		cout << "0\n";
		return;
	}
	cout << maxheap.front() << "\n"; // print max value
	maxheap[0] = maxheap.back();
	maxheap.pop_back();
	int idx = 0;
	int child = idx * 2 + 1;
	while (child < maxheap.size()) {
		// child = current node's bigger child
		if (child + 1 < maxheap.size() && maxheap[child] < maxheap[child + 1]) child++;
		if (maxheap[idx] >= maxheap[child]) break; // if current node is bigger than children, there is no need to move down
		swap(maxheap[idx], maxheap[child]);
		idx = child;
		child = child * 2 + 1;
	}
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input
	int N;
	cin >> N;

	// operation
	vector<ll> maxheap;
	for (int i = 0; i < N; i++) {
		ll x;
		cin >> x;
		if (x > 0) I(maxheap, x);
		else D(maxheap);
	}

	return 0;
}

BOJ 1927번: 최소 힙 (실버 II)

https://www.acmicpc.net/problem/1927

 

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

이번엔 최소 힙의 구현입니다.

#include <iostream>
#include <vector>
using namespace std;

#define ll long long

void I(vector<ll>& minheap, ll x) {
	minheap.push_back(x); // insert at end position
	int idx = minheap.size() - 1;
	while (idx > 0 && minheap[(idx - 1) / 2] > minheap[idx]) {
		// if parent is bigger, swap and move to the parent
		swap(minheap[idx], minheap[(idx - 1) / 2]);
		idx = (idx - 1) / 2;
	}
}

void D(vector<ll>& minheap) {
	if (minheap.empty()) {
		cout << "0\n";
		return;
	}
	cout << minheap.front() << "\n"; // print min value
	minheap[0] = minheap.back();
	minheap.pop_back();
	int idx = 0;
	int child = idx * 2 + 1;
	while (child < minheap.size()) {
		// child = current node's smaller child
		if (child + 1 < minheap.size() && minheap[child] > minheap[child + 1]) child++;
		if (minheap[idx] <= minheap[child]) break; // if current node is smaller than children, there is no need to move down
		swap(minheap[idx], minheap[child]);
		idx = child;
		child = child * 2 + 1;
	}
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input
	int N;
	cin >> N;

	// operation
	vector<ll> minheap;
	for (int i = 0; i < N; i++) {
		ll x;
		cin >> x;
		if (x > 0) I(minheap, x);
		else D(minheap);
	}

	return 0;
}

BOJ 11286번: 절댓값 힙 (실버 I)

https://www.acmicpc.net/problem/11286

 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

절댓값이 가장 작은 원소가 루트에 있도록 하는데, 절댓값이 같은 경우 원소 값이 작아야 함에 유의합니다.

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

#define ll long long

bool compare(ll x, ll y) {
	if (llabs(x) != llabs(y)) return llabs(x) > llabs(y);
	return x > y;
}

void I(vector<ll>& heap, ll x) {
	heap.push_back(x); // insert at end position
	int idx = heap.size() - 1;
	while (idx > 0 && compare(heap[(idx - 1) / 2], heap[idx])) {
		// if parent's absolute value is bigger, swap and move to the parent
		swap(heap[idx], heap[(idx - 1) / 2]);
		idx = (idx - 1) / 2;
	}
}

void D(vector<ll>& heap) {
	if (heap.empty()) {
		cout << "0\n";
		return;
	}
	cout << heap.front() << "\n"; // print min value
	heap[0] = heap.back();
	heap.pop_back();
	int idx = 0;
	int child = idx * 2 + 1;
	while (child < heap.size()) {
		// child = current node's smaller child
		if (child + 1 < heap.size() && compare(heap[child], heap[child + 1])) child++;
		if (!compare(heap[idx], heap[child])) break; // if current node is smaller than children, there is no need to move down
		swap(heap[idx], heap[child]);
		idx = child;
		child = child * 2 + 1;
	}
}

int main() {
	// using cin & cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// input
	int N;
	cin >> N;

	// operation
	vector<ll> heap;
	for (int i = 0; i < N; i++) {
		ll x;
		cin >> x;
		if (x != 0) I(heap, x);
		else D(heap);
	}

	return 0;
}

유의사항을 고려해 비교 함수를 따로 구현해 주었습니다.

BOJ 5639번: 이진 검색 트리 (골드 V)

https://www.acmicpc.net/problem/5639

 

5639번: 이진 검색 트리

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다

www.acmicpc.net

이진 검색 트리라는 조건이 있기에, 전위 순회만 알려 줬지만 중위 순회도 아는 것이나 다름없습니다.

#include <cstdio>
#include <algorithm>
using namespace std;

int preorder[10000];

void postorder(int left, int right) {
	if (left >= right) return;
	int* inorder = new int[right - left];
	for (int i = 0; i < right - left; i++) {
		inorder[i] = preorder[left + i];
	}
	sort(inorder, inorder + right - left);
	const int root = preorder[left];
	int idx = find(inorder, inorder + right - left, root) - inorder;
	postorder(left + 1, left + 1 + idx);
	postorder(left + 1 + idx, right);
	printf("%d\n", root);
}

int main() {
	// input
	int node;
	int i = 0;
	while (scanf("%d", &node) == 1) {
		preorder[i++] = node;
	}

	// output
	postorder(0, i);

	return 0;
}

 

문제풀이: 우선순위 큐

BOJ 7662번: 이중 우선순위 큐 (골드 IV)

https://www.acmicpc.net/problem/7662

 

7662번: 이중 우선순위 큐

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적

www.acmicpc.net

우선순위 큐를 구현하는데, 최대값과 최소값을 모두 관리할 수 있어야 합니다.

#include <iostream>
#include <set>
using namespace std;

int main() {
	// using faster cin & cout
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// input
	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		int k;
		cin >> k;
		multiset<int> Q;
		for (int i = 0; i < k; i++) {
			char op;
			int n;
			cin >> op >> n;
			if (op == 'I') {
				Q.insert(n);
			}
			else if (op == 'D') {
				if (Q.empty()) continue;
				else if (n == 1) Q.erase(--Q.end());
				else if (n == -1) Q.erase(Q.begin());
			}
		}
		if (Q.empty()) cout << "EMPTY\n";
		else cout << *Q.rbegin() << " " << *Q.begin() << "\n";
	}

	return 0;
}

multiset을 쓰면 나름대로 쉽게 해결할 수 있습니다. 하지만, 직접 구현한다면 어려울 수 있는 문제였어요.

BOJ 2075번: N번째 큰 수 (실버 I)

https://www.acmicpc.net/problem/2075

 

2075번: N번째 큰 수

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

www.acmicpc.net

#include <iostream>
#include <queue>
using namespace std;

#define ll long long

int main() {
	// using faster cin & cout
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// input line 1
	int N;
	cin >> N;

	// using priority queue
	priority_queue<int, vector<int>, greater<int>> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ll num;
			cin >> num;
			q.push(num);
		}
		while (q.size() > N) {
			q.pop();
		}
	}
	
	cout << q.top();

	return 0;
}

우선순위 큐를 사용하는데, 메모리 제한이 타이트해서 큐의 사이즈를 주기적으로 줄여주었습니다.

BOJ 11000번: 강의실 배정 (골드 V)

https://www.acmicpc.net/problem/11000

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

www.acmicpc.net

#include <iostream>
#include <queue>
using namespace std;

#define ll long long

struct meeting {
	ll begin;
	ll end;
};

bool operator>(meeting left, meeting right) {
	if (left.begin != right.begin) return left.begin > right.begin;
	return left.end > right.end;
}

int main() {
	// using faster cin & cout
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// input line 1
	int N;
	cin >> N;

	// input line 2 ~ N + 1
	priority_queue<meeting, vector<meeting>, greater<meeting>> q; // sort by begin time, then end time (ascending)
	for (int i = 0; i < N; i++) {
		meeting m;
		cin >> m.begin >> m.end;	
		q.push(m);
	}

	// room scheduling
	priority_queue<ll, vector<ll>, greater<ll>> room;
	while (!q.empty()) {
		if (!room.empty() && room.top() <= q.top().begin) {
			// the first ending class ends before new class begins
			room.pop(); // we can use existing room
		}
		room.push(q.top().end); // update new class end time
		q.pop();
	}

	// output
	cout << room.size();

	return 0;
}

꽤 생각을 잘 해야 하는 문제로, 우선 수업들을 먼저 시작하는 순서대로 (똑같이 시작하면, 먼저 끝나는 순서대로) 정렬해 둬야 합니다. 그 뒤 room이라는 이름의 우선순위 큐에 각 수업이 끝나는 시간을 집어넣는데, 만약 수업이 시작하는 시간보다 '가장 먼저 끝나는 수업의 끝나는 시간'이 더 이르다면 그 강의실에 수업을 집어넣으면 되니, '가장 먼저 끝나는 수업'을 우선순위 큐에서 제거하고 이 수업이 끝나는 시간을 새로 집어넣습니다.

BOJ 1715번: 카드 정렬하기 (골드 IV)

https://www.acmicpc.net/problem/1715

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

#include <iostream>
#include <queue>
using namespace std;

int main() {
	// using faster cin & cout
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// input line 1
	int N;
	cin >> N;

	// input line 2 ~ N + 1
	priority_queue<int, vector<int>, greater<int>> q;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		q.push(num);
	}

	// operation
	int ops = 0;
	while (q.size() > 1) {
		int a = q.top();
		q.pop();
		int b = q.top();
		q.pop();
		q.push(a + b);
		ops += a + b;
	}

	// output
	cout << ops;

	return 0;
}

카드의 묶음을 우선순위 큐에 넣고 가장 적은 것 두 개를 계속 뽑아서 더하고 더한 묶음을 넣는 것을 반복하면 됩니다.


즐겁다! 다음 주제는 그래프 탐색입니다. (DFS와 BFS)