-
Heavy-Light Decomposition Recursive DP
개요 Heavy-Light Decomposition Heavy-Light Decomposition(HLD)은 루트 있는 트리를 여러 개의 heavy chain으로 분할하는 알고리즘으로, 다음의 성질들을 만족합니다. 각 간선은 heavy edge 또는 light edge로 분류됩니다. 리프가 아닌 정점은 자식들 중 정확히 하나를 heavy child로 갖습니다. heavy child로 가는 간선은 heavy edge이고, 다른 자식으로 가는 간선은 모두 light edge입니다. heavy edge로 연결된 정점들의 묶음을 heavy chain이라 합니다. 각 heavy chain의 형태는 한 정점에서 출발해서 리프까지 내려가는 연속적인 경로가 되고, 모든 정점은 정확히 하나의 heavy chain에 속하게...
-
Heavy-Light Decomposition
서론 알고리즘 문제를 풀다 보면 많은 경우에 문제를 그래프 문제로 모델화할 수 있음을 보게 됩니다. 여러 요소들간의 관계가 주어지는 경우에는 각 요소를 정점으로, 관계를 간선으로 두는 방식의 모델화가 자주 사용되고, DP 문제는 대다수의 경우 DAG(Directed Acyclic Graph)의 형태로 각 상태가 이어지게 되므로 역시 그래프 문제의 일종으로 볼 수 있습니다. 그런데 특별한 제약 조건이 없는 그래프 문제의 경우 이 모델화에 성공하면 대체로 문제가 쉬워지거나, 전형적인 알고리즘을 요구하는 문제로 바뀌게 됩니다. 오히려 제약 조건이 추가된 형태일수록 그...