센트로이드 분할 - Centroid Decomposition

서론

이 글은 센트로이드 분할 알고리즘을 이해하기 전에 먼저 센트로이드를 찾는것을 알아보는 글입니다.
센트로이드를 처음 접한다면 굉장히 난해하고 이해하기 어려울 수 있습니다. 한번 개념을 잘못 이해하면 센트로이드의 정의를 이해를 하지 못할 수 있습니다. 그러므로 이 글은 센트로이드 분할을 하기에 앞서 센트로이드가 어떻게 생기는 것인지 이해하는것이 목표입니다.

센트로이드를 완전 처음 접한다면 이 글 을 읽어보거나 이 영상 을 보는것을 추천합니다. 저 글에서 알려주는 센트로이드를 증명하는 귀류법을 완벽하게 이해한다면 이 글을 읽지 않아도 괜찮습니다.

센트로이드

1. 센트로이드를 구하는 이유

센트로이드는 트리에서의 분할정복을 위해서 고안된 알고리즘 입니다.
일반적으로 분할정복은 수열에서 이루어지는데, 시작점 start 와 끝점 end 가 있을 때, 중간점 mid = (start+end)/2 을 잡고 start 와 mid 사이 , mid 와 end 사이를 재귀적으로 탐색하면서 두 점 사이의 차가 같거나 1 일 때 특정 연산을 한 후 그 값을 토대로 넓은 범위에서 구하려는 값을 작은 범위에서 구한 값을 통해 계산해서 점진적으로 범위를 넓힌 후 전체 탐색 범위의 값을 구하는 과정입니다.

merge sort 나 segment tree 를 공부한다면 분할정복이 어떠한 상황에서 쓰이는지 쉽게 이해할 수 있습니다.

분할정복의 장점은 계속해서 절반 씩 쪼갠다는 점인데, 정점이 $N$ 개가 있으면 $N/2$ 씩 계속 탐색하여 시간복잡도가 $O(NlogN)$ 이 됩니다.

따라서 분할정복을 통한 시간복잡도의 효과를 누리기 위해 센트로이드를 사용합니다.

2. 센트로이드란?

분할정복을 하기 위해서는 분할되는 조각들이 $N/2$ 이하로 줄여들어야 합니다.
수열의 길이가 10인데 , 1과 9로 나누고 , 다시 9를 1과 8로 나누면 $O(logN)$ 이 아니라 $O(N)$ 과 다를바 없기 때문입니다.

수열에서는 단순히 길이의 중간값을 찾으면 되지만 트리에서는 다른 방법을 써야합니다.
트리를 아래와 같이 정의하겠습니다.

• 정점의 개수가 $N$개인 트리 $T$ 가 있다.
• 트리에서 임의의 정점 $V$ 를 선택하고 , $V$ 를 제거했을 때 여러개의 서브트리가 발생한다.
• 그러한 서브트리중 크기가 가장 큰 서브트리를 $maxSize(V)$ 라고 정의한다.
• 이 때 $maxSize(V)$ 가 $N/2$ 보다 작거나 같다면 $V$ 정점은 센트로이드이다.

위 내용을 그림을 통해 설명하겠습니다.

위의 트리에서 임의의 정점을 선택해야 합니다. 13번 노드를 선택하고, 제거해보겠습니다.

13번 노드를 제거한다면 서브트리가 2개로 나누어집니다. 각각 크기가 12 와 2 입니다.
이 중 가장 큰 서브트리의 크기는 12 이므로 $maxSize(13)$ 은 12 입니다.

하지만 13번 노드를 제거하는건 분할정복을 함에 있어서 적절하지 않은 선택입니다.
매번 절반씩 크기를 줄여서 $O(logN)$ 만큼 줄여야 하는데 전체 크기가 15인 노드에서 절반 크기인 7보다 훨씬 큰 12인 서브트리를 탐색해야 하기 때문입니다. 즉 , $maxSize(13)$ 은 $N/2$ 보다 큽니다.

따라서 이번엔 중심점인 1번 노드를 제거해보겠습니다.

1번 노드를 제거한다면 위 처럼 여러개의 서브트리들이 생겨납니다.
서브트리의 크기는 시계방향으로 1 , 3 , 3 , 7 입니다.

이러한 서브트리중 가장 크기가 큰 서브트리는 왼쪽의 서브트리이므로 $maxSize(1)$ 은 7 이 됩니다.
이번에는 $maxSize(1)$ 이 $N/2$ 보다 작습니다.

따라서 정점 1번은 센트로이드입니다.

여기서 한가지 내용을 추가하겠습니다.

• 트리 $T$ 에서 $maxSize(V)$ 가 가장 작은 정점을 구한다. 그 정점을 $X$ 라고 한다.

즉, 임의의 정점 $V$ 를 제거했을때 생기는 여러개의 서브트리중 가장 큰 서브트리인 $maxSize(V)$ 를 구했을 때 그 값이 가장 작은 정점을 구하는 것입니다. 그 정점을 $X$ 라고 하겠습니다.

사실 $V$ 또한 정점이기 때문에 $maxSize(V)$ 가 가장 작은 정점 $V$ 를 구한다는것과 같은 의미지만 그 정점이 특별하기 때문애 $V$ 가 아니라 $X$ 라고 정의하겠습니다.

그러면 2번 노드부터 15번 노드까지 $maxSize$ 를 구해보겠습니다. 1번노드는 이전에 $maxSize(1)$ 이 7 이었습니다.

3. $maxSize(V)$ 가 가장 작은 정점을 구하기

2번 노드를 제거시 $maxSize(2)$ 는 14 입니다.

3번 노드를 제거시 $maxSize(3)$ 는 12 입니다.

4번 노드를 제거시 $maxSize(4)$ 는 14 입니다.

5번 노드를 제거시 $maxSize(5)$ 는 14 입니다.

6번 노드를 제거시 $maxSize(6)$ 는 8 입니다.

7번 노드를 제거시 $maxSize(7)$ 는 12 입니다.

8번 노드를 제거시 $maxSize(8)$ 는 14 입니다.

9번 노드를 제거시 $maxSize(9)$ 는 14 입니다.

10번 노드를 제거시 $maxSize(10)$ 는 12 입니다.

11번 노드를 제거시 $maxSize(11)$ 는 14 입니다.

12번 노드를 제거시 $maxSize(12)$ 는 14 입니다.

13번 노드를 제거시 $maxSize(13)$ 는 12 입니다.

14번 노드를 제거시 $maxSize(14)$ 는 13 입니다.

15번 노드를 제거시 $maxSize(15)$ 는 14 입니다.

따라서 1번 정점을 선택했을 때 $maxSize(1)$ 은 7 로써 가장 작습니다.

4. 센트로이드 존재의 증명

지금까지 $maxSize(V)$ 를 구하고 그 값이 최소가 되는 정점을 구했습니다.

이를 한 이유는 센트로이드의 존재를 증명하기 위해서 입니다.

• 모든 트리에서는 센트로이드가 항상 존재한다.

위 정의를 증명하기 위해 귀류법을 사용하겠습니다.
즉, 위 정의를 거짓이라고 했을 때 논리적 모순을 보임으로써 반대로 위 정의가 참일 수 밖에 없도록 만들어 보겠습니다.

• 센트로이드가 없는 트리 $T$ 가 있다.
• 트리 $T$ 에서 $maxSize(V)$ 가 가장 작은 정점을 구한다. 그 정점을 $X$ 라고 한다.
• 정점 $X$ 를 제거하고 생기는 서브트리중 가장 큰 서브트리 $T1$ 은 $N/2$ 보다 크다.
  왜냐하면 트리 $T$ 에는 센트로이드가 존재하지 않기 때문이다.

귀류법을 적용하여 센트로이드가 없는 트리를 가정했을 때 위와 같은 결론에 다다르게 됩니다.

이전의 센트로이드의 정의는 아래와 같았습니다.

• $maxSize(V)$ 가 $N/2$ 보다 작거나 같다면 $V$ 정점은 센트로이드이다.

그리고 한가지 내용을 추가하겠습니다.

• $T1$ 에서 $X$ 와 인접한 정점을 $Y$ 라고 하면, $maxSize(X) > maxSize(Y)$ 이다.

왜 $maxSize(X) > maxSize(Y)$ 가 성립할까요?
전제 조건에서 센트로이드가 없다고 가정했습니다. 그리고 $maxSize(V)$ 가 가장 작은 정점인 $X$ 를 구했을 때 생기는 가장 큰 서브트리 $T1$ 을 생각해봅시다.
$T1$ 에서 $X$ 와 인접한 정점 $Y$ 는 $T1$ 의 루트 노드가 됩니다.
여기서 정점 $Y$ 를 제거해서 $maxSize(Y)$ 를 구한다고 생각해보겠습니다. 이 부분이 중요합니다.

$Y$ 를 제거한다면 $X$ 와 인접한 부분과 $X$ 와 인접하지 않은 부분으로 나뉩니다.
$X$ 와 인접한 부분을 생각해봅시다.

$T1$ 은 정점 $X$ 를 제거하고 생긴 서브트리중 가장 큰 서브트리이가 $N/2$ 보다 크기 때문에 반대로 $T1$ 이 아닌 부분들, 즉 $X$ 를 제거하고 남은 나머지 서브트리들은 $N/2$ 보다 작습니다. 작거나 같지 않은 이유는 $X$ 를 제거했기 때문에 $N/2$ 작거나 같은 크기와 $N/2$ 보다 큰 서브트리의 합은 $N$ 이 될 수 있지만 이미 $X$ 노드 하나를 뺀 상태에서 $N$ 보다 작아야 하기 때문입니다.

그렇다면 $X$ 와 인접하지않는 부분은 어떨까요?
정점 $Y$ 가 제거되면서 여러 서브트리들로 나뉘게 될것입니다. $T1$은 루트노드가 $Y$ 인 트리지만 , 루트노드가 사라짐으로써 여러 서브트리가 발생하게 됩니다.

이때, 자식이 1개인경우를 생각하면 $T1$ 이 $maxSize(X)$ 크기이므로 $X$ 와 인접한 정점인 $Y$ 를 제거한다면 $maxSize(Y)$ 는 $maxSize(X)-1$ 이 될것입니다.

자식이 2개이상인 경우를 생각하면 서브트리들이 더 많이 생겨나 각 서브트리들의 크기가 더 작아질것이기 때문에 $maxSize(Y)$ 는 $maxSize(X)-1$ 보다 더 작은 값이 됩니다.

따라서 $maxSize(X) > maxSize(Y)$ 입니다.

하지만 위 식은 모순 됩니다.
왜냐하면 우리가 정의한 $maxSize(X)$ 는 아래와 같기 때문입니다.

• 트리 $T$ 에서 $maxSize(V)$ 가 가장 작은 정점을 구한다. 그 정점을 $X$ 라고 한다.

즉 $maxSize(X)$ 보다 작은건 없습니다. 그런데 $maxSize(Y)$ 가 $maxSize(X)$ 보다 작다고 결론이 나왔기 때문에 모순이 생긴겁니다.

여기서 알 수 있는 사실은 트리 $T$ 에 센트로이드가 없다고 가정하면 모순이 생기고, 결국 트리 $T$ 에는 센트로이드가 존재할 수 밖에 없다는 사실입니다.

즉 임의의 정점 $V$ 를 제거했을 때 쪼개지는 서브트리의 크기가 $N/2$ 보다 크다면 그 서브트리안에 센트로이드는 존재할 수 밖에 없습니다.

그림을 통해 정말로 그런지 확인해보겠습니다.

그림에 있었던 트리에서는 $maxSize(V)$ 가 가장 작은 정점인 $X$ 가 바로 1번 노드였습니다.
그 값은 7 이었고요.

그리고 $X$ 노드, 즉 1번 노드를 제거했을때 생기는 서브트리중 가장 큰 부분은 바로 왼쪽 부분이었습니다. 즉 $T1$ 은 왼쪽 서브 트리를 의미하며, 1번노드가 있던 그림에서 $T1$ 에서 1번노드와 인접한 정점 $Y$ 는 바로 6번 노드가 됩니다.

그러면 6번 노드를 제거했을 때 그림을 보겠습니다.

이때 $maxSize(6)$ 은 8이 됩니다.
따라서 $maxSize(1) < maxSize(6)$ 입니다.
이는 그림을 통해서 $maxSize(X) > maxSize(Y)$ 식이 모순됨을 알 수 있습니다.

그리고 추가적으로 알 수 있는 사실은 $maxSize(V)$ 가 $N/2$ 보다 크다면 그 서브트리안에 센트로이드가 있다는 것입니다.

위 그림에서 6번을 지운 3개의 서브트리중, 오른쪽이 가장 큰 서브트리가 되며 그 서브트리안에 센트로이드 정점이 있습니다. 그 정점이 바로 1번 노드입니다.

결론적으로 우리는 트리에 센트로이드가 존재한다는 것을 증명했습니다.

이후에는 센트로이드를 통해 어떻게 분할정복을 하는지 알아보겠습니다.