Week 2
- 우선순위 큐, 힙
- C++를 이용한 우선순위큐 프로그래밍 방법
- 백준 1966번 - 프린터 큐
- 백준 1655번 - 가운데를 말해요
<우선순위 큐>
일단 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First in First Out) 형식의 자료구조이다.
우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.
<힙>
- 힙(Heap)은 우선순위 큐를 위해 만들어진 완전이진트리 형태의 자료구조이다.
- 반 정렬상태를 유지하는 완전이진트리이다. (= 부모노드와 서브트리간 대소 관계가 성립된다.)
오름차순이나 내림차순으로 우선순위 큐를 구현하는 것보다 삽입과 삭제를 하는 평균시간이 적어서 훨씬 유리하다. (O(log₂n))
- 최대 힙 (Max Heap)
부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리
key(부모노드) ≥ key(자식노드)
- 최소 힙 (Min Heap)
부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리
key(부모노드) ≥ key(자식노드)
<C++를 이용한 우선순위큐 프로그래밍 방법>
#include <queue>
우선순위 큐는 queue를 include하여 사용한다.
- 선언
priority_queue<자료형, Container, 비교함수> 변수명
선언한 자료형 변수들을 비교함수에 따라 정렬하는 Priority_Queue(우선순위큐)를 선언
- 추가 및 삭제
push : Priority_Queue에 원소를 삽입 ( 비교함수에 따라 내부적으로 정렬됨)
pop() : 맨 앞에 있는 원소를 삭제
- 기타
empty() : Priority_Queue가 비어있으면 true 아니면 false를 반환
top() : Priority_Queue에서 가장 높은 우선순위를 반환
size() : Priority_Queue의 크기 반환
swap() : 두 개의 Priority_Queue를 swap한다.
<백준 1966번 - 프린터 큐>
#include <iostream>
#include <queue>
using namespace std;
int main() {
int count = 0;
int test_case;
cin >> test_case;
int n, m, ipt;
for (int i = 0; i < test_case; ++i) {
count = 0;
cin >> n >> m;
queue<pair<int, int>> q;
priority_queue<int> pq;
for (int j = 0; j < n; ++j) {
cin >> ipt;
q.push({ j, ipt });
pq.push(ipt);
}
while (!q.empty()) {
int index = q.front().first;
int value = q.front().second;
q.pop();
if (pq.top() == value) {
pq.pop();
++count;
if (index == m) {
cout << count << endl;
break;
}
}
else q.push({ index,value });
}
}
}
일단 우선순위 큐를 이용하여 푸면 쉽게 풀 수 있다. 먼저 큐에 인덱스와 그 인덱스에 해당하는 중요도의 값을 넣는다.
큐가 빌 때까지 현재 중요도와 우선순위 큐에 있는 중요도를 확인하고 현재 인덱스와 내가 찾고자하는 인덱스 값이 일치할 때까지 반복한다.
<백준 1655번 - 가운데를 말해요>
#include<iostream>
#include<queue>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
priority_queue<int> max;
priority_queue<int, vector<int>, greater<int>> min;
while (t--) {
int a, size;
cin >> a;
if (max.size() == min.size()) {
max.push(a);
}
else {
min.push(a);
}
if (!max.empty() && !min.empty() && max.top() > min.top()) {
int max_val, min_val;
max_val = max.top();
min_val = min.top();
max.pop();
min.pop();
max.push(min_val);
min.push(max_val);
}
cout << max.top() << '\n';
}
return 0;
}
일단 우선순위 큐 2개를 선언해야한다. max큐 1개, min큐 1개를 선언한다. max 큐의 top 값이 min큐의 top값 보다 클 경우, max큐와 min큐의 top 값을 swap해준다. 따라서 max큐의 top 값에 전체수가 짝수일 시 작은수를 , 전체수가 홀수일 시 중간 값을 출력한다.