HW2

1. 우선순위 큐와 힙

1.1 우선순위 큐(Priority Queue)

우선순위 큐는 우선순위의 개념을 큐에 도입한 자료구조이다. 보통의 큐는 선입선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 된다. 그러나 우선순위 큐는 데이터들이 우선순위를 가지고 있어 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 출력된다.

우선순위 큐를 구현하는 방법에는 세 가지가 있다. 배열, 연결리스트, 힙을 사용하는 것이다. 단순 배열과 연결 리스트 기반의 우선순위 큐 모델은 두 가지 방법 모두 최악의 경우 새 데이터의 위치를 찾기 위해서 기존에 저장된 모든 데이터와 비교를 진행해야 한다.

우선순위 큐는 삭제 연산에서 어떤 요소가 먼저 삭제되는가에 따라 최소 우선순위 큐와 최대 우선순위 큐로 나누어진다. 최대 우선순위 큐는 우선순위가 가장 높은 요소가 먼저 삭제되고, 최소 우선순위 큐는 가장 우선순위가 낮은 요소를 먼저 삭제한다.

1.2 힙(Heap)

영단어 heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 가진다. 힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 부모 노드의 키 값이 자식 노드의 키 값보다 큰 완전 이진 트리를 말한다. 즉, A가 B의 부모 노드라고 하면 key(A)≥key(B)가 항상 성립한다.

힙의 구현은 배열을 기본으로 하며 인덱스가 0인 요소는 비워둔다. 따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다는 중요한 특징을 가진다. 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다. 우선순위를 나타내는 정수 값이 작을 수록 높은 우선순위를 나타낸다고 가정한다.

루트 노드로 올라갈 수록 저장된 값이 커지는 완전 이진 트리를 가리켜 최대 힙(max heap)이라고 한다.

루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 가리켜 최소 힙(min heap)이라고 한다.

2. C++을 이용한 우선순위 큐 프로그래밍 방법

#include <iostream>
#include <queue>
#include <functional>
using namespace std;
  
int main()
{
  //우선순위 큐 선언
  priority_queue<int> pq;
  
  //우선순위 큐에 원소를 삽입
  pq.push(1);
  pq.push(3);
  pq.push(6);
  pq.push(2);
  pq.push(11);
    
  //큐가 비어있지 않다면 무한반복, 비어있다면 반복문을 실행하지 않는다
  while(!pq.empty()){
  	cout << pq.top() << "\n";
  	pq.pop();
  }
  return 0;
}

[출력 결과]

3. 문제 풀이

3-1. 백준 1966번 - 프린터 큐

[문제]

[문제 정리]

[풀이]

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

int main(void) {
    int count = 0;
    int num_test_cases;
    cin >> num_test_cases;
    int N, M, ipt; //문서의 개수, 궁금한 문서 위치, 중요도

    for (int i = 0; i < num_test_cases; ++i) {
        count = 0;
        cin >> N >> M;
        priority_queue<int> pq; // 우선순위 큐
        queue<pair<int, int>> q;

        for (int j = 0; j < N; ++j) {
            cin >> ipt;
            q.push({ j, ipt });
            pq.push(ipt);
        }
        while (!q.empty()) {
            // index 값과 우선순위 값을 가져온 뒤 pop
            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 });
        }
    }
    return 0;
}