사용자 도구

사이트 도구


ps:센트로이드_분할

센트로이드 분할 (Centroid Decomposition)

센트로이드

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

센트로이드 찾기

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

센트로이드 분할

  • To be filled

토론

댓글을 입력하세요:
J Q J I C
 
ps/센트로이드_분할.txt · 마지막으로 수정됨: 2022/10/12 06:07 저자 teferi