PS와 우선순위 큐
알고리즘 문제를 풀다보면 끊임없이 만나는 자료구조가 있다.
바로 우선순위 큐이다.
C++에서 priority_queue를 사용하다보면 강력함도 느끼고, 동시에 한계도 많이 느낀다.
오늘은 이에 대해 다루어보려고 한다.
우선순위 큐의 활용
LeetCode - Find Median from Data Stream
Find Median from Data Stream - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
위 문제를 한번 풀어보겠다.
문제조건은 위와 같다. 정수 입력이 주어지고, 이 입력들의 중위수를 구하는 문제이다.
함수는 API 구현형 문제이며 크게 addNum(), findMedian() 이 두 함수를 구현하면 된다.
간단히 생각하면 findMedian() 호출시 배열을 정렬하여 중위수를 뽑을 수 있겠지만,
- At most 5 * 10^4 calls will be made to addNum and findMedian.
위 제약사항이 문제가 된다.
Worst case에 50,000번 nlogn 비용의 정렬을 돌린다면...
따라서 findMedian()을 매번 호출할 때마다 정렬하는 것은 좋은 방법이 아니다.
우선순위 큐 사용하기
그러면 정렬하는 비용을 절약하면서, findMedian()의 중위수를 한 번에 찾을 방법은 무엇이 있을까?
정답부터 말하자면, 우선순위 큐 두개를 사용하면 된다.
[0, n]의 정렬된 데이터가 있다고 가정할 때, [0, n/2-1]은 MAX_Q에, [n/2, n]은 MIN_Q에 넣는 것이다.
각설하고 코드부터 보자면 아래와 같다.
그림으로 설명하자면, 아래와 같다.
좌측에는 MAX_Q를, 우측에는 MIN_Q를 두어 매번 값을 삽입할 때마다 그 값이 좌측 큐의 top보다 작으면 좌측에 삽입, 그 값이 우측 큐의 top보다 크면 우측에 삽입하는 것이 기본 아이디어이다.
이 방법으로 다른 방법들보다 꽤나 빨리 풀 수 있다.
중위수를 찾는데 탐색비용이 O(1)이기 때문에 새로운 데이터를 add 할 때 좌우측 큐의 top을 잠깐 스왑하는 오버헤드는 그렇게 크지 않다.
우선순위 큐 활용 스킬
우선 순위 큐를 잘 활용하여 데이터 탐색시간의 최적화를 잘 해보고 싶은데, 문제가 하나있다.
큐에 이미 삽입되어 있는 데이터가 실시간으로 갱신된 경우 큐의 업데이트가 불가능하다는 것이다.
여기서 해결책은 두가지가 될 수 있겠는데,
1. 수정된 데이터를 New data로 만들어서 PQ에 다시 삽입하는 것
* Lazy update: 새로운 데이터를 삽입만하고 기존 데이터는 flag로 체크
* PQ.pop()하면서 flag에 체크된 alive 상태가 살아있는 경우만 사용하도록, 이외는 버림
간략화한 코드는 아래와 같다.
- priority_queue<pair<int, Data*>> PQ에서 Data는 그대로 재활용
- 여기서 pri는 modify시 변경, 삽입하여 pop시 최신의 pri 배열의 값과 비교
이를 그림으로 표현하면 아래와 같다.
여기서, A', B'는 새로 PQ에 삽입된 A, B의 각각 갱신된 데이터이고 A, B는 따로 삭제되지 않은 채 PQ내에 신규 데이터와 함께 공존한다.
코드에서 설명된 것과 같이 큐의 top을 찾는 과정에서 flag처리된 A, B 노드들은 버려질 것이다.
2. 직접 PQ에 데이터에 대한 구현하기
이 경우에는 문제조건에 따라 구현이 많이 달라질 수 있다.
마치며
PQ는 분명히 효과적인 방법이기는 하나 제약사항을 많이 가지고 있다.
PQ는 정렬된 데이터를 가져올 때 매우 효과적으로 사용할 수 있지만 데이터의 삭제/변경이 잦은 경우 링크드리스트 혹은 Set이 더 나을 수도 있다.
PQ의 데이터를 삭제하는 비용은 비싸기에 Lazy update와 같은 방법으로 대안을 생각해볼 수도 있지만, 삭제/변경의 오버헤드가 매우 커지는 상황이라면 그 비용을 잘 계산하여 Set의 iterator를 이용하여 데이터를 직접 삭제하는 방법 등을 생각해볼 수 있겠다.
