알고리즘/그래프
2021. 10. 13.
Centroid Decomposition
Centroid Decomposition에 대해 알아봅시다. Centroid Decomposition을 이용하면 트리에서 분할정복을 사용할 수 있게 됩니다. https://anz1217.tistory.com/17 분할 정복 (Divide and Conquer) 분할 정복은 큰 문제를 분할하여 단순한 부분 문제로 만든 다음, 각 부분 문제의 답으로부터 전체 문제의 답을 이끌어내는 방식의 알고리즘입니다. 역시 분할 정복 자체만으로 풀 수 있는 문제 anz1217.tistory.com 위의 글에서 히스토그램에서 가장 큰 직사각형을 찾는 문제를 어떻게 풀었는지 다시 한 번 생각해봅시다. 히스토그램을 반으로 나눕니다. 그러면 답은 히스토그램의 왼쪽 절반, 오른쪽 절반, 또는 양쪽에 모두 걸쳐서 존재합니다. 한 절..
