테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 센트로이드 분할 (Centroid Decomposition) ======
  * 참고: [[https://justicehui.github.io/hard-algorithm/2020/08/25/centroid/]]

===== 센트로이드 =====
  * 센트로이드는 정점 하나를 지웠을때 쪼개지는 서브트리의 크기가 모두 전체 트리의 절반 이하가 되게하는 노드를 말한다.
  * 모든 트리에는 1개 또는 2개의 센트로이드가 존재한다.
  * 트리에서 센트로이드를 찾는 것은, 트리에서 분할정복을 하기 위한 기준점으로 사용하기 위해서 필요하다.
    * 1차원 배열에서 중간점을 기준으로 두조각으로 분할해서 분할정복을 하는 것과 같은 원리이다.

==== 센트로이드 찾기 ====
  * 알고리즘은 간단하다. 임의의 센트로이드 1개를 찾기 위해서는 다음처럼 하면 된다.
    * 1) 임의의 노드를 루트로 잡고, 모든 노드에 대해서 그 노드를 루트로 하는 서브트리의 크기를 계산한다.
    * 2) 루트에서부터 출발해서, 현재 노드에 달려있는 서브트리중 크기가 N/2 초과인것이 있는지 찾는다. 그런 서브트리가 없으면, 그 노드가 센트로이드. 그런 서브트리가 있으면 그 노드를 현재 노드로 세팅하고 다시 2)를 반복.
    * 총 시간복잡도는 O(n)
  * 관련 문제: [[ps:problems:boj:7045]]


===== 센트로이드 분할 =====
  * To be filled