[C++ STL] 참고지식

백준의 "강의실 배정" 문제를 풀면서 이전에 생각하지 못한 STL 사용법을 알게되어 작성하게 되었다.

stack, queue, vector와 같이 특정 주제가 있다기 보단,
코드를 작성하는 과정에서 '이게 될까?' 싶었던 부분에 대해 알게된 내용을 작성하려고 한다.

1. 시간복잡도
   sort 함수 : O(NlogN)
   priority_queue : O(logN)

   이전에는 편의상 sort 함수를 그냥 썼지만, "강의실 배정" 문제를 푸는 과정에서 O(NlogN)의 시간복잡도를 만족하기 위해 처음으로 찾아보게 됐다.
   sort 함수의 경우, 입력의 크기가 매우 큰 경우에는 사용을 할 수 없을 것 같다.

   또한, priority_queue의 경우 트리를 구성하는 성분의 수 N에 따라서 push 혹은 pop이 발생할 때 O(logN)의 연산 횟수를 갖는 것을 알 수 있었다.

   특히, priority_queue에 대해 좀 더 친숙해져서 "강의실 배정"과 같은 문제에서 자연스럽게 응용할 수 있으면 좋겠다.

2. pair 자료구조에 대한 sort함수
   pair 자료구조는 first와 second를 가지고 있기 때문에, sort 함수에 대해 적용할 수 없을 것으로 생각했다.
   하지만 "강의실 배정" 문제를 푸는 과정에서 실험해본 결과,

   1) 먼저 first를 기준으로 오름차순 정렬
   2) 중복되는 first에 대해서는 second를 비교하여 오름차순 정렬

   하는 것을 알 수 있었다.

   이전까지는 pair 자료구조는 sort 함수를 사용할 수 없을 것으로 생각하여, 직접 구조체를 선언하고 연산자 오버로딩을 하여 직접 정렬을 설정했다.
   하지만 앞으로는 이럴 필요없이 모든 성분에 대해 오름차순 정렬이 필요하면 pair 자료형을 갖는 vector에 바로 sort 함수를 적용하면 유용할 것 같다.
   

3. priority_queue 선언 및 인자
   이전까지는 priority_queue를 사용할 때 항상 다음과 같이 정의하여 사용했다.

   priority_queue<int> pq;

   위와 같이 선언하면 max_heap이 필요한 경우는 그대로 사용하면 되지만, min_heap이 필요한 경우는 priority_queue에 push/pop 할 때 음수처리를 해서 삽입해야하는 불편함이 있었다.

   따라서 앞으로는 min_heap이 필요한 경우, 다음과 같이 정의하여 사용할 수 있다.

   priority_queue<int, vector<int>, greater<int> > pq;

   여기서 첫번째 인자 int는 자료형을 의미하고, 두번째 인자 vector는 priority_queue가 vector 위에서 동작하고 있다는 구현체를 의미한다. 해당 인자는 vector 외에 deque를 입력해도 가능하다고 하지만, 기본적으로 vector를 입력하는 것 같다.
   세번째 인자는 비교 연산자로, greater<자료형>을 입력하면 작은 순서로(오름차순) 정렬한다.
   참고로 기본적으로 less<자료형>이 정의되어 있기 때문에 처음과 같은 방식으로 선언해도 max_heap이 선언될 수 있었다.
   

위와 같은 깨알 지식들이 유용하게 쓰일 일이 있으면 좋겠다.