개념 설명만 NMK번 듣고 구현은 아직도 마스터하지 못한 그것을 제대로 각잡고 구현해보려 한다. 간단하게 센트로이드의 개념 설명을 좀 하면, 어떤 트리에서 어떤 정점의 서브트리들 중 가장 정점의 개수가 많은 서브트리의 크기가 전체 트리의 정점 수의 절반 이하일 때, 이 정점을 센트로이드라고 한다. 트리의 총 정점 수가 짝수 개일 때, 센트로이드는 2개가 존재하며, 트리의 총 정점 수가 홀수 개일 때, 센트로이드는 단 하나만 존재한다. 이 센트로이드 정점을 기준으로 트리를 분할 정복하여 $O(N^2)$의 시간복잡도를 가지는 풀이를 $O(NlogN)$의 시간복잡도를 가지도록 최적화할 수 있고, 이를 센트로이드 분할 기법이라고 부른다. BOJ 20297 Confuzzle 문제를 기준으로 구현해보려 한다. 일단..