[자료구조] 우선순위 큐(Priority Queue) - 백준 1781(컵라면)과 백준 2109 (순회강연) 풀면서 알아보기

Priority Queue(우선순위 큐)에 대해서는 면접에서 한번 질문을 받은 적이 있었다. 사실 그때는 그냥 외운것을 다시 읊조리는 정도의 답변만 했었다. 그러다 최근데 코딩테스트를 준비하면서 백준 1781번(컵라면) 문제와 백준 2109(순회강연) 문제를 풀면서 우선순위 큐에 대해서 제대로 학습하게 된 계기가 되었다.

 

두 문제를 어떻게 풀었고, 우선순위 큐로 인한 차이가 어떻게 발생했는지, 왜 그러했는지 정리를 하면서 우선순위 큐에 대한 내용을 머리에 다시한번 꾸깃꾸깃 넣어본다.

 

문제 풀이 로직은 아래 github 링크를 참조하여 주기를 바라며, 이 글은 우선 순위 큐에 대해서 정리하고자 한다.

---

백준 1781(컵라면) - 링크

백준 2109(순회강연) - 링크

풀이언어 : C++ ( C++에서 우선 순위 큐 사용 방법 - 링크 )

풀이 링크 : GitHub

연관 문제 : 백준 14729(칠무해) - 링크

---

문제 설명

두 문제는 그리디 알고리즘의 대표적인 문제이다. 그리디 알고리즘은 최적해를 구하는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식이다. 그리디 알고리즘이 잘 작동하는 문제는 대부분 두가지를 충족한다.

• greedy choice property : 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는 다는 것
• optimal substructure : 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해

위 두조건을 충족되어 정답을 내야하는 코테문제 입장에서는 '최적이 되는 기준'을 정해서 정렬을하거나 우선순위 큐를 사용하면 쉽게 풀수 있다고 한다. ( 큰돌의 알고리즘 강의 )

 

순회 강연 문제와 컵라면 문제는 구조가 동일한 문제이다. 다만 차이가 있다면 입력 조건이다.

- 순회 강연은 n의 범위가 0 ~ 10,000으로 주어진다.

- 컵라면 문제는 1 ~ 200,000이 주어진다.

- 둘다 시간 제한은 2초이다.

 

나는 해당 입력을 처음에는 c++ 자료구조인 vector에 담았다. 그리고 이것을 sort 했다.

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

int N;
int main(void){

    vector<p> v;
    cin >> N;

    for(int i = 1; i <= N; i++){
        int d, c;
        cin >> d >> c;
        v.push_back(make_pair(d,c));
    }

    sort(v.begin(), v.end());
    
    ... 중략
}

 

순회 강연 문제는 이렇게 sort를 하여 풀어도 문제가 없었다. 그러나 컵라면 문제에서는 제출 결과 시간 초과가 발생했다.

 

 

문제 해결 방법

문제의 구조가 동일한데, 시간초과가 발생하였고 미리 위에서 언급했지만 입력의 크기를 의심했고 입력의 방식이 틀렸다는 것을 시간이 꽤나 흐르고 나서야 알았다. 아래와 같이 우선 순위큐로 받았을 때 시간 초과가 발생하지 않았다.

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

struct cmp{
bool operator()(pair<int, int>&a, pair<int, int>&b) {
              if (a.first == b.first) {
                  return a.second > b.second;
              }
              else {
                  return a.first > b.first;
              }
          }
};

int N;
int main(void){

    vector<p> v;
    cin >> N;


    priority_queue<p, vector<p>, cmp > vv;
    for(int i = 1; i <= N; i++){
        int d, c;
        cin >> d >> c;
        vv.push(make_pair(d,c));
    }
    
    ... 중략
}

 

 

무엇이 문제였을까?

최대 입력을 벡터로 저장하여 정렬을 하면 처리 속도가 얼마가 걸릴 것인가?

STL에서 사용하는 sort 알고리즘은 n log(n)의 시간복잡도를 가지는 정렬 알고리즘을 사용한다. ( Hybrid of QuickSort, HeapSort and InsertionSort ) 그렇기에 최대 입력이 최악의 시간으로 주어진다면 n^2이 발생할 수 있다. 입력기준 400억이고 측정 방식과 사양에 따른 차이는 있겠지만 백준에서 CPU 1초 연산 속도가 대략 1억번 연산이 가능하다고 하니 40초가 걸려버린다. 시간 초과다.

 

반면 우선순위큐를 사용하면 어떨까? (대게 최대 힙으로 구현되어 있기에) 힙으로 구현된 우선순위 큐를 사용한다고 하면 최악의 시간 복잡도가 n log(n)이다. 최대 입력이 주어져도 대략 100만이고 1/100초에 수행이 가능하게 된다.

 

즉 이러한 문제에서는 입력과 동시에 정렬이 가능한 형태로 우선순위 큐를 사용하면 풀이가 용이하겠다. 입력에서 우선순위 큐를 사용하여 풀이를 고려할만한 문제로 백준 14729번 (칠무해) 문제가 있다.

 

 

정리 : 그래서 우선순위 큐란?

면접 답변 형태로 한번 정리를 해보자

 

우선순위 큐란 선입 선출의 자료구조이나, 저장 데이터의 우선순위에 따라 정렬 된 결과를 선입 선출하게 되는 자료구조이다.

우선순위 큐는 최대 힙으로 구현되는 것이 일반적이나, 연결리스트나 배열로도 구현이 가능하다.

( 최대 힙 : 부모 노드가 자식 노드 보다 값이 큰 완전 이진트리 )

시간 복잡도는 아래와 같다

 

구현 방법	삽입 시간 복잡도	삭제 시간 복잡도	정렬 시간복잡도 - 최악
배열	O(N)	O(1)	N * log(N) - N^2
힙	O(logN)	O(logN)	logN - N * log(N)

 

시간 복잡도에 대해서 짧고 빠르게 이해를 원한다면 링크 참고

 

 

더 알아보기

다음에 글을 쓰겠지만, 트리에 대해서 정리해본다.