-
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에 속하게...
-
Euler Tour 테크닉
문제 상황 다음과 같은 문제를 생각해 보자. (루트가 있는) 트리 $T$가 있다. 모든 정점은 초기에 $0$의 가중치를 가지고 있다. 이 때, 다음 두 종류의 질의를 처리해보자. 정점 $v$와 새로운 가중치 $x$가 입력으로 주어질 때, 정점 $v$의 가중치를 $x$로 바꾼다. 정점 $x$와 $x$의 모든 후손들(즉, 정점 $x$를 루트로 한 부트리의 정점들)의 가중치의 합을 구한다. 생각할 수 있는 가장 쉬운 풀이들은 $arr[x]$를, 정점 $x$의 가중치로 정의한다. 1번 질의는 상수 시간에 처리할 수 있다. 2번 질의에서 일일히 정점...
-
트리 압축
개요 트리에 관한 문제를 풀다 보면, 일부 정점만이 쿼리로 들어왔는데 모든 정점을 검사하기에는 비효율적인 경우가 있습니다. 이 때 필요 없는 정점과 간선들을 지워서 새로운 트리를 만드는 기법을 트리 압축이라고 부릅니다. 다른 말로는 Virtual Tree / Auxiliary Tree라고도 합니다. 다음 예시를 통해 트리 압축이 정확히 무엇인지와 어떻게 구현하는지에 대해서 살펴보겠습니다. JOI Open Contest 2014. 공장들 정점이 $N$개인 간선 가중치 트리와 $Q$개의 쿼리가 주어집니다. $i$번 쿼리마다 서로소인 두 정점 부분집합 $S_i$와 $T_i$가 주어지면, $S_i$의 한 정점에서 $T_i$의...
-
Centroid of a Tree
Centroid of a Tree Centroid는 트리에서 문제를 해결하는 경우에 중요한 역할을 하는 경우가 많습니다. 이번 글에서는 트리에서 정의되는 centroid가 무엇인지, 어떤 성질을 가지고 있는지 그리고 어떻게 사용하는지 등을 알아보고자 합니다. Centroid 트리에서 centroid는, 어떤 정점 $v$가 크기 $n$짜리 트리 $T$에서 삭제했을 경우 생기는 subtree들이 모두 각각 크기가 $n/2$ 이하가 되는 경우, $v$를 $T$의 centroid라고 합니다. 위 그림에서는 1번 노드가 centroid 입니다. 1을 삭제했을 때 각각 크기가 3, 4, 4인 서브트리가 생기고 전체 트리의 크기는 11이므로...
-
Skew-binary Lifting
Table Of Contents Prerequisite Introduction Implementation Performance Analysis Benchmark Prerequisite Binary Lifting - Tutorial on cp-algorithms Introduction 안녕하세요, Aeren입니다! 이 글에서 소개할 내용은 skew-binary number system을 기반으로 한 skew-binary lifting입니다. 이 글은 An Applicative Random-Access Stack by Eugene W. MYERS을 기반으로 작성되었습니다. 일반적인 binary lifting과의 차이점 중 하나는 각 node $u$가 $O(\log(\textrm{depth}[u]))$ 대신 $O(1)$ 만큼의 공간을 필요로 한다는 것입니다. 표로 정리하면 다음과 같습니다. (Time) / (Additional Space Required) Operation Binary Lifting Skew-binary Lifting Add A...
-
Minimum Cuts in Near-Linear Time
Introduction Weighted graph $G$에 대해, $G$의 min-cut 혹은 edge connectivity 는 $G$의 connected component가 둘 이상이 되도록 하기 위해 제거해야 하는 가중치 합으로 정의됩니다. 이름 그대로 네트워크를 단절시키기 위해 필요한 최소 비용으로, 수많은 파생과 응용이 가능합니다. 이 글에서는 $n$개의 정점, $m$개의 간선을 가진 weighted graph $G$의 min-cut을 near-linear time ($\tilde{O}(m)$)에 구하는 최초의 방법인 D. R. Karger의 Minimum Cuts in Near-Linear Time을 리뷰합니다. Definition 그래프 $G$는 non-negative weighted graph로 가정합니다. 즉, weight는 음 아닌 실수 값을...
-
APIO 2020
APIO 2020 올해 학생들 성적은 1금5은으로 예년과 비슷한 편으로 보인다. 반딧불이 300점 만점에 300점을 받아서, 2015년 이후 첫 APIO 만점과 함께 금메달을 얻었다. 반딧불 학생은 올해 IOI 국가대표이기도 한데, 아직 고등학교 1학년이니 앞으로도 좋은 결과가 기대된다. 그 뒤를 이어 이온조, 최서현, 장태환, 김지훈, 최은수 학생이 은메달을 얻었다. 모두 축하합니다! 1. 벽 칠하기 Subtask 1 (12점) 특정 벽을 칠할 수 있는 일꾼이 누구인지 고정되어 있다. 고로 색에 대해서 신경쓸 필요가 없고, 각 일꾼들이 문제의 조건에 맞게...
-
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms 그래프의 최소 컷 (Minimum cut) 은 그래프를 연결되지 않게 하기 위해서 지워야 하는 간선의 최소 개수, 혹은 간선 가중치의 최소 합이다. 만약 간선의 최소 개수로 컷을 정의한다면, 최소 컷은 그래프의 connectivity 를 정의하는 수량이 된다. 고로 최소 컷은 그래프가 주어졌을 때 계산하고 싶은 가장 기초적인 수량에 해당되며, 응용 예시 또한 무수히 많다. 그래프의 최소 컷을 계산하는 방법은 크게 3가지가 있다. 아래에 해당 방법의 발견 시간 순으로 나열한다. (아래...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 4)
동적 계획법을 최적화하는 9가지 방법 (Chapter 4) 이 글은 Chapter 3에서 계속된다. 9. Dynamic Tree DP Dynamic Tree DP는 특수한 형태의 Tree DP를 최적화할 수 있는 방법으로, 일반적인 직선에서 행렬과 같은 구조를 사용하여 DP를 최적화하는 것과 비슷한 방식이다. 사실 Tree DP가 아니라 일직선에서 하는 DP 문제라 하더라도 최적화 방법이 자명하지 않기 때문에, 이 글에서는 먼저 일직선에서의 DP 최적화를 먼저 설명한다. (일직선에서의 이러한 DP 최적화를 부르는 말은 잘 모른다.) In Line 다음과 같은 문제를 생각해 보자....
-
Heavy-Light Decomposition
서론 알고리즘 문제를 풀다 보면 많은 경우에 문제를 그래프 문제로 모델화할 수 있음을 보게 됩니다. 여러 요소들간의 관계가 주어지는 경우에는 각 요소를 정점으로, 관계를 간선으로 두는 방식의 모델화가 자주 사용되고, DP 문제는 대다수의 경우 DAG(Directed Acyclic Graph)의 형태로 각 상태가 이어지게 되므로 역시 그래프 문제의 일종으로 볼 수 있습니다. 그런데 특별한 제약 조건이 없는 그래프 문제의 경우 이 모델화에 성공하면 대체로 문제가 쉬워지거나, 전형적인 알고리즘을 요구하는 문제로 바뀌게 됩니다. 오히려 제약 조건이 추가된 형태일수록 그...
-
Tree Isomorphism
소개 안녕하세요. 이번 글에서는 Tree Isomorphism에 대해 소개해드리려고 합니다. Isomorphism이란 어떤 두 대상이 수학적으로 동등한 관계에 있음을 나타내는 용어인데, 트리에서의 Isomorphism이라 하면 한쪽 트리의 정점을 적절히 renumbering했을 때 다른 한 쪽 트리와 같아지는 것을 말합니다. (정확히는 그러한 mapping을 가리킵니다.) 이해를 돕기 위해, 다음과 같이 두 개의 트리가 있다고 합시다. 딱 보면 두 트리의 모양이 달라보이지만, 오른쪽 트리의 정점을 아래와 같이 renumbering하면 왼쪽 트리와 완전히 같은 연결 관계를 갖게 됩니다. 즉, 두 트리는 isomorphic합니다. 이처럼 두...
-
이진탐색의 확장 - 트리에서의 효율적인 탐색
서론 이진탐색은 정렬된 $N$개의 원소가 있을 때, 원하는 수의 위치를 $O(\log N)$ 시간에 찾는 테크닉이다. 이 글에서는 이진탐색을 트리로 확장할 것이다. 그리고 트리에서도 원하는 수의 위치를 $O(\log N)$시간에 찾을 수 있다는 증명과, 비교연산을 최소로 하는 방법을 설명할 것이다. 이진탐색 탐색이란 숨겨진 $a$ 이상 $b$이하의 정수 $x$에 대해, 이 $x$를 찾는 과정이다. 이진탐색에서는 다음과 같은 질문을 할 수 있다: “어떤 수 $y$ 에 대해, $y$와 $x$의 대소관계는 무엇인가?” $y$가 $x$보다 크다는 답이 돌아오면, 우리는 $x$가 $y+1$...