-
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\)...