edenooo

Queue Undo Trick

개요 최근에 소개된 아이디어라 한글 자료가 없어서 글을 작성하게 되었습니다. 자료구조의 업데이트 연산이 Amortized 시간복잡도를 갖지 않는다면 가장 최근에 한 업데이트를 취소하는 롤백 연산도 같은 시간복잡도에 구현할 수 있음이 알려져 있습니다. 이 글에서는 롤백 연산의 아이디어를 활용한, 가장 오래된 업데이트를 취소하는 Queue-Undo 연산에 대해 소개합니다. 이 연산은 기존의 Offline Dynamic Connectivity 알고리즘과는 달리 온라인으로 동작한다는 장점을 가지고 있습니다. 유니온-파인드 자료구조에 Queue-Undo 연산을 구현해서 연습 문제들을 해결할 것이기 때문에, 사전 지식으로 유니온 파인드를 알고 있음을 가정하고...