august14님께서 BOJ에서 이벤트를 개최하셨습니다. (이벤트 공지)
다항시간 안에 해결하지 못하는 문제를 적절히 잘 풀어나가는 이벤트로, 재미있어 보이길래 참가했습니다. 이벤트가 2일만에 끝나서 아쉽긴 하지만, 여러가지 시도를 많이 해봤고 오랜만에 재밌게 문제를 풀 수 있었습니다.
3월 16일에 이벤트가 끝나면 올릴 생각이었지만 일찍 끝났길래 지금 올립니다.
이 글에서는 2일동안 제가 이 문제를 풀기 위해 시도한 것들을 정리합니다.
어떤 자료구조가 “persistent하다”라는 것은, 상태의 변화가 생기더라도 과거 상태를 모두 보존하고 있다는 것을 의미합니다.
Persistent Segment Tree(PST)는 세그먼트 트리의 갱신 과정을 모두 저장하고 있는 자료구조입니다.
평범하게 세그먼트 트리를 구현하면 공간복잡도는 O(N)입니다. 이런 문제를 생각해봅시다.
0으로 초기화된 길이 N인 수열이 있을 때, 수 하나를 변경하는 쿼리와 구간의 합을 구하는 쿼리가 총 Q개 주어집니다. 이때 N ≤ 1,000,000,000이고 Q ≤ 100,000이고, 쿼리가 들어올 때마다 해당 쿼리에 대한 답을 내야 합니다.(온라인 쿼리)
세그먼트 트리는 분할 정복을 메모이제이션하는 자료구조라고 할 수 있고, 이런 성질을 통해 다양한 문제를 해결할 수 있습니다.
이 글에서는 분할 정복을 이용하는 합병 정렬(Merge Sort)을 메모이제이션하는 Merge Sort Tree와 이것을 이용해 해결할 수 있는 문제들을 다룹니다.
어떤 문제에서 답이 단조성을 가질 때는 binary search 등을 이용한 parametric search로 빠르게 답을 구할 수 있습니다.
병렬 이분 탐색(Parallel Binary Search, PBS)는 parametric search의 각 결정 문제를 스위핑 하듯이 풀 수 있는 몇몇 경우에 적용할 수 있는 기법입니다. 말로 설명하기 힘드니 문제와 함께 소개하겠습니다.