-
Priority Queue Undo Trick
도입 어떤 자료구조 $D$에 대해 다음 세 연산을 지원해야 하는 상황을 생각해 보자. Push(u, p): 우선순위 $p$를 가진 업데이트 $u$를 $D$에 적용한다. Pop: 현재 $D$에 적용된 업데이트 중 우선순위가 가장 높은 것을 취소한다(undo). Query: $D$에 쿼리를 수행한다. 이 연산들의 조합은 표준 우선순위 큐와 비슷해 보이지만, 핵심 차이는 $D$에 대한 undo를 지원해야 한다는 점이다. 만약 Pop이 항상 가장 최근에 적용한 업데이트를 취소한다면 단순한 스택 + rollback으로 해결된다. Pop이 FIFO 순서라면 이 블로그에 소개된 Queue-like Undoing Trick으로...
-
임의의 원소를 수정할 수 있는 우선순위 큐
서론 힙 (Heap)은 그 간단한 구조와 시간 / 공간 측면에서의 여러 장점들 때문에 문제 풀이뿐만 아니라 실무에서도 우선순위 큐로서 널리 애용되는 자료구조입니다. C++의 std::priority_queue, Java의 java.util.PriorityQueue, Python의 heapq1 등 고수준 언어의 자료구조 라이브러리에서 웬만하면 지원을 해주기도 합니다. 우선순위 큐를 라이브러리로만 접하면 기능이 매우 적은 것에 대해 실망할 수도 있습니다. 대체로 원소를 삽입하는 기능과, 최대 혹은 최솟값을 확인하고 제거하는 연산이 전부이기 때문입니다. 그런데 사실 힙에는 그 외에도 많은 가능성들이 숨어있습니다. 단순한 형태의 구현체에서는 수행하기 어려운 연산들을...