Elevation

본래 무게중심이라는 뜻의 단어인 센트로이드(centroid)는, 트리에서 하나의 정점을 제거했을 때 나눠지는 서브 트리의 정점의 개수가 원래 정점의 개수의 절반 이하가 되도록 하는 정점으로 정의된다. 따라서 센트로이드를 찾으면 트리를 균형 있게 분할하는 것이 가능하다. 몇 가지 센트로이드에 대한 직관적이고도 중요한 성질들이 있다. 트리에는 센트로이드가 항상 존재한다.센트로이드는 1개 혹은 2개 존재한다.센트로이드가 2개 존재하는 경우, 두 센트로이드는 서로 인접해 있다. 트리에서 분할 정복을 수행하려는 경우, 고른 root에 따라 최악에는 트리의 깊이가 정점 수 $N$까지 늘어날 수 있어 시간이 오래 걸릴 우려가 있다. 이럴 때 전체 트리의 센트로이드 $u$를 찾은 뒤, $u$에 대해 처리를 완료한 후 ..

아호-코라식(Aho-Corasick) 알고리즘은 다중 문자열 서칭, 즉 하나의 문자열 $T$ 내에서 여러 개의 패턴 문자열 $P_1, P_2, \cdots, P_k$를 찾아야 하는 과제에서 사용 가능한 강력한 알고리즘이다. 아이디어는 매우 직관적이며 단순한데, 찾아야 하는 패턴 문자열들로 트라이(trie)를 만들고, 트라이 내에서 KMP를 수행하는 것이다. 다만 트라이와 kmp 둘 다 다소 복잡한 구조의 알고리즘이다 보니 구현이 간단한 편은 아니다. KMP의 핵심인 실패 함수가 트라이 위에서 어떻게 동작하는지를 이해하는 것이 아호-코라식의 핵심이라고 할 수 있다. 실패 함수의 구성KMP의 작동 원리를 다시 떠올려 보자. $j-1$까지 일치하다가 $j$에서 불일치하는 경우, $j := fail[j-1]$..

나는 문자열 알고리즘을 개인적으로 별로 좋아하지 않는데, 특히 kmp는 유난히 이해가 잘 되지 않아서 계속 글 쓰기를 미뤄놓고 있었다. 하지만 class 6에 kmp 문제가 등장하기도 하고 슬슬 한번쯤 다뤄야 할 주제인 것 같아 정리해 본다. KMP(Knuth-Morris-Pratt) 알고리즘은 단일 문자열 서칭에 있어 가장 강력한 알고리즘 중 하나이다. 문자열 $T$ 내에서, 찾아야 하는 대상인 패턴 문자열 $P$가 어디에 등장하는지 구하는 문제가 주어졌다고 가정해 보자. $T$의 모든 인덱스를 시작점으로 하여 패턴과의 일치 여부를 비교하는 경우 최악에는 두 문자열 길이의 곱인 $O(NM)$만에 동작할 것이다. 물론 $P$가 길지 않은 경우에는 큰 문제가 없으며 패턴과 일치하지 않는 순간 바로 brea..

세그먼트 트리는 구간 쿼리에 특화되어 있어, 주어진 $[L, R]$ 구간의 합이나 최댓값/최솟값을 구하는 문제를 $O(\log N)$만에 잘 처리해 준다. 문제는 업데이트가 점 단위가 아닌 구간으로 주어지는 경우에 발생한다. 한 번의 점 단위 업데이트를 진행할 때 $O(\log N)$이 소요되므로, 일일이 구간 내 모든 값을 업데이트하는 것은 비효율적이다. 느리게 갱신되는 세그먼트 트리는 구간에 대한 정보를 담고 있는 세그먼트 트리의 구조를 십분 활용하여 구간 단위 업데이트를 $O(\log N)$만에 수행한다. lazy propagation의 원리기본 세그먼트 트리의 아이디어는 구간 쿼리를 처리할 때 구간 내에 포함되는 노드 밑으로는 더 이상 내려가지 않고 바로 결과를 반환하는 것이었다. 마찬가지로 l..

고속 푸리에 변환은 합성곱(convolution)을 빠르게 처리하기 위해 사용되는 알고리즘이다. $$ F \ast G = \sum_k F[k] G[t-k] $$ 합성곱은 이산 공간에서 위와 같이 정의된다. 변수의 합을 $t$로 고정시켜 놓고, $k$를 움직여 가며 누적한 결과라고 이해하면 되겠다. 가장 대표적인 상황은 두 다항식을 곱했을 때, 차수가 $t$인 항의 계수를 구하는 경우일 것이다. 합성곱을 정의 그대로 구현하면 당연히 $O(N^2)$이 소요되겠지만, fft를 사용하면 $O(N \log N)$만에 합성곱을 구할 수 있다. 이산 푸리에 변환FFT를 이용해 합성곱을 구하는 과정은 다음과 같이 진행된다. 길이 $N$인 배열 $F, G$ 각각을 먼저 푸리에 변환($F_f , G_f$)한다. 변환 시..

개미(BOJ 14942)를 보자. 문제 자체는 정말 단순한데, 각 정점별로 dfs하는 간단한 해법을 떠올릴 수 있다. 그러나 트리가 일자로 깊은 구조라면, $O(N^2)$의 시간이 소요되어 시간 초과를 받게 될 것이다. 따라서 depth가 깊은 경우 빠르게 조상으로 거슬러 올라가는 방법이 필요하다. 희소 배열희소 배열(sparse table) 자료 구조가 이 문제를 해결해 준다. 아이디어는 매우 간단한데, 각 노드의 부모를 저장하는 parent 배열을 2차원으로 확장시켜 다음과 같이 정의하는 것이다. $parent[i][k]$ = ($i$번 노드의 $2^k$번째 조상) 부모는 1번째 조상이므로 k=0에 해당한다. 2번째 조상을 구할 때는 부모의 부모를 찾으면 되며, 4번째 조상은 2번째 조상의 2번째 ..

트리는 그래프 시리즈만큼 내용상 순차적으로 잘 연결되게 연재하지는 않을 것 같다. 트리가 정의상 그래프의 부분집합이기도 하고, 겹치는 아이디어가 꽤 있기 때문이다. 세그먼트 트리 등의 경우 이미 잘 설명하고 있는 다양한 출처가 존재하는 것도 한몫한다. 그럼에도 불구하고 트리는 자료 구조의 측면에서 활용되고 설명할 거리가 많아 그래프와는 분리하였다. 여기서는 어느 정도의 그래프 이론 지식이 있음을 전제하고 설명한다. 트리의 정의와 특성사이클이 없는 연결 그래프를 트리(Tree)라고 한다. 이 단순한 정의로부터 다양한 특성들이 도출된다. 정점이 $N$개인 트리의 간선 수는 $N-1$개이다.모든 간선은 단절선(bridge)이 된다. 즉 간선을 없애면 그래프가 분리된다.반대로 (중복 및 self-loop가 아..