etyu

(이 글은 독자가 Splay tree, link/cut tree를 이해하고 있다고 가정하고 설명한다.) Top tree는 동적 트리 (간선의 추가, 제거가 일어나는 트리)를 관리하는 자료구조이다. Top tree는 path 쿼리와 subtree 쿼리를 모두 지원하며, 트리의 diameter, center, median과 같은 일반적인 자료구조에서 관리하기 힘든 값들을 관리할 수 있다. 이 글은 Self-Adjusting Top Tree 논문에 기반하여 Top Tree의 구현에 대해 설명한다. (이 논문에 대해서 구사과님이 쓰신 글도 있다.) Top tree 직선형 구조를 관리하는 자료구조인 세그먼트 트리는 전체 배열을 여러 구간으로 분리하고, 이 구간들을 합치는 과정을 트리로 관리한다. Top tree는..

Dynamic Connectivity Problem(동적 연결성 문제)란, 다음과 같은 쿼리를 처리하는 문제를 말합니다. 임의의 간선 추가 임의의 간선 삭제 어떤 두 정점 사이에 경로가 존재하는지 판별 이 문제는 분할 정복을 통해 오프라인으로 풀 수 있지만, 이 글에서는 온라인 풀이를 설명합니다. 그래프가 포레스트일 때 포레스트에서는 Link-Cut Tree나 Euler Tour Tree를 사용하여 풀 수 있습니다. 이번에는 Euler Tour Tree를 사용합니다. 어떤 트리를 Euler Tour로 나타낸 수열에서 그 트리를 복원할 수 있기 때문에 각 트리를 트리 자체가 아닌 Euler Tour로 관리합니다. 이렇게 관리하면 간선의 추가, 삭제는 이 수열을 끊고 연결하는 연산들로 대체할 수 있습니다. ..

이 글은 다음 논문(EERTREE: An Efficient Data Structure for Processing Palindromes in Strings)을 바탕으로 작성된 글입니다. 이 글의 그림은 이 논문에서 가져왔습니다. 개요 Eertree는 문자열의 회문을 관리하는 자료구조입니다. Eertree를 설명하기에 앞서, 몇가지 정의를 내리고 시작하겠습니다. 문자열은 \(w = w[1..n]\)과 같이 표현하고, 문자열의 i번째 문자는 S[i]와 같이 표현합니다. 문자의 종류의 수를 \(\sigma\)로 표현합니다. 어떤 \(i, j\)에 대해 \(u = w[i..j]\)라면 \(u\)는 \(w\)의 부분 문자열(substring)입니다. 어떤 \(i\)에 대해 \(u = w[1..i]\)라면 \(u\)..

홀의 결혼 정리(Hall's marriage theorem)는 여러 개의 집합이 주어졌을 때, 각 집합에서 서로 다른 수를 고를 수 있는 필요충분조건에 대한 정리입니다. 홀의 결혼 정리에 의하면, 집합들의 집합 \(S = \{A_1, A_2, \dots, A_k\}\)가 주어졌을 때 각 집합에서 서로 다른 수를 고를 수 있다는 것은 어떤 \(S\)의 부분집합 \(W\)을 선택하더라도 \(W\)의 원소들의 합집합의 크기가 \(|W|\) 이상이라는 것과 동일합니다. CERC 2016. Bipartite Blanket 더보기 먼저 이분 그래프의 두 정점 집합에서 매칭이 존재하는 정점 부분집합을 따로 구해봅시다. 전부 \(O(2^n + 2^m)\)개의 경우가 있으므로 각각 홀의 결혼 정리를 만족하는지 검사한 뒤..