ps:센트로이드_분할
센트로이드 분할 (Centroid Decomposition)
센트로이드
- 센트로이드는 정점 하나를 지웠을때 쪼개지는 서브트리의 크기가 모두 전체 트리의 절반 이하가 되게하는 노드를 말한다.
- 모든 트리에는 1개 또는 2개의 센트로이드가 존재한다.
- 트리에서 센트로이드를 찾는 것은, 트리에서 분할정복을 하기 위한 기준점으로 사용하기 위해서 필요하다.
- 1차원 배열에서 중간점을 기준으로 두조각으로 분할해서 분할정복을 하는 것과 같은 원리이다.
센트로이드 찾기
- 알고리즘은 간단하다. 임의의 센트로이드 1개를 찾기 위해서는 다음처럼 하면 된다.
- 1) 임의의 노드를 루트로 잡고, 모든 노드에 대해서 그 노드를 루트로 하는 서브트리의 크기를 계산한다.
- 2) 루트에서부터 출발해서, 현재 노드에 달려있는 서브 트리중 크기가 N/2 초과인것이 있는지 찾는다. 그런 서브트리가 없으면, 그 노드가 센트로이드. 그런 서브트리가 있으면 그 노드를 현재 노드로 세팅하고 다시 2)를 반복.
- 총 시간복잡도는 O(n)
- 관련 문제: Tree Cutting
센트로이드 분할
- To be filled
ps/센트로이드_분할.txt · 마지막으로 수정됨: 2022/10/12 06:07 저자 teferi
토론