Elevation

개미(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가 아..