Tree Optimization

트리에서 사용할 수 있는 특수한 몇몇 알고리즘들은 실제 시간복잡도가 생각한 것보다 작을 수 있다. 이 글에서는 그런 몇몇 케이스를 다룬다.

~

노드 개수가 \(A\)인 서브트리의 결과와 노드 개수가 \(B\)인 서브트리의 결과를 \(O(AB)\)의 시간에 합칠 수 있는 경우

최악의 경우 \(A\)와 \(B\)가 모두 \(O(N)\), 합치는 횟수가 \(O(N)\)이므로 \(O(N^3)\)인 것 같지만, 사실 \(O(N^2)\)이다.

~

증명

노드 개수가 \(N\)인 서브트리의 결과를 만드는 데 필요한 시간을 \(T(N)\)이라고 정의하자.

또한, 노드 개수가 \(A\)인 서브트리의 결과와 노드 개수가 \(B\)인 서브트리의 결과를 합치는 데 \(cAB\) (\(c\)는 상수) 이하의 시간이 필요하다고 하자.

\(N<A+B\)인 모든 \(N\)에 대해 \(T(N) \le cN^2\)이라고 가정하면,

\[T(A+B) \le T(A) + T(B) + cAB \le cA^2 + 2cAB + cB^2 = c(A+B)^2\]

따라서 수학적 귀납법에 의해 시간복잡도가 \(O(N^2)\)이 된다.

~

응용

이 아이디어로 ACM-ICPC Daejeon Regional 2012 J번(Slicing Tree), Coder's high 2016 Round 2: Nexon Arena C번(트리의 변화), shake! 2017 F번(단신쓴짠)을 풀 수 있다.

~

루트가 있는 트리에서, 각 노드마다 (자식들 중 높이가 두 번째로 높은 노드의 높이 + 높이가 세 번째로 높은 노드의 높이 + ... + 높이가 가장 낮은 노드의 높이)의 합으로 문제를 풀 수 있는 경우

이 경우 시간복잡도가 \(O(N)\)이다.

~

증명

노드 \(u\)의 높이를 \(h_u\)라고 하자. 높이의 정의에 따라, 노드 \(u\)의 자식들 \(v\)에 대해 \(h_u = \max_v \{h_v\} + 1\)이다.

또한, 루트를 제외하고 모든 노드의 부모는 단 한 개이므로, 트리의 루트를 \(r\)이라고 하면 모든 노드에 대해 모든 자식들의 높이 합은 다음과 같다.

\[\sum_{u \neq r} h_u = \sum_u h_u - h_r\]

모든 노드에 대해 두 번째, 세 번째, ...로 높이가 높은 노드의 높이 합은 전체 높이 합에서 첫 번째로 높이가 높은 노드의 높이 합을 뺀 것과 동일하다.

\[\sum_{u \neq r} h_u - \sum_u \max_v \{h_v\} = \sum_u h_u - \sum_u \max_v \{h_v\} - h_r = \sum_u ( h_u - \max_v \{h_v\} ) - h_r = N - h_r = O(N)\]

~

응용

이 아이디어로 가중치 없는 트리에서 세 정점의 순서쌍 (u, v, w)에 대하여, (u-v의 거리) = (v-w의 거리) = (w-u의 거리)를 만족하는 순서쌍이 몇 개나 있는지를 \(O(N)\)으로 구할 수 있다.

이 문제를 \(O(N^2)\)으로 풀면 만점이 나오는 버전이 POI에 출제되었다.

Archive: https://main.edu.pl/en/archive/oi/21/hot

Baekjoon Online Judge: https://www.acmicpc.net/problem/10122

Baekjoon Online Judge에서 \(O(N)\) 풀이로 0ms를 받았으니, 관심이 있는 분은 \(O(N^2)\) 풀이로 맞은 뒤 코드를 읽어보시기 바랍니다.