-
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Expander Decomposition and Pruning: Faster, Stronger, and Simpler 알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 예를 들어서, Heavy Light Decomposition은 트리에서 큰 문제를 부분 문제로 나누는 과정에서 자주 등장한다. 각 문제가 쉽고 (직선), 합치는 것이 가능 (Light edge를 통해서 묶음) 하기 때문이다. 트리의 경우에는 HLD 외에도 다양한 분할 정복 기법이 존재하지만, 그래프를 분할 정복하는...
-
Queue Undo Trick
개요 최근에 소개된 아이디어라 한글 자료가 없어서 글을 작성하게 되었습니다. 자료구조의 업데이트 연산이 Amortized 시간복잡도를 갖지 않는다면 가장 최근에 한 업데이트를 취소하는 롤백 연산도 같은 시간복잡도에 구현할 수 있음이 알려져 있습니다. 이 글에서는 롤백 연산의 아이디어를 활용한, 가장 오래된 업데이트를 취소하는 Queue-Undo 연산에 대해 소개합니다. 이 연산은 기존의 Offline Dynamic Connectivity 알고리즘과는 달리 온라인으로 동작한다는 장점을 가지고 있습니다. 유니온-파인드 자료구조에 Queue-Undo 연산을 구현해서 연습 문제들을 해결할 것이기 때문에, 사전 지식으로 유니온 파인드를 알고 있음을 가정하고...
-
Segment의 개수를 이용하는 순열 경우의 수 문제
소개 특정 조건을 만족하는 순열의 개수를 세는 문제 중에서, segment(이하 구간)의 개수를 이용하는 특이한 꼴의 다이나믹 프로그래밍 문제를 다뤄보려고 합니다. 예시 문제를 통해 살펴봅시다. 문제1. 길이가 $N$, Increasing segment의 개수가 $K$개인 순열의 개수 Increasing segment란, $l+1 \leq i \leq r$인 모든 $i$에 대해 $A_{i-1} < A_i$를 만족하는 $[l, r]$이라고 합니다. 단, 다른 increasing segment에 포함되는 구간은 무시하는 걸로 합시다. 예를 들어, $1\space4\space5\space2\space3\space6\space8\space7$의 increasing segment는 $[1, 3], [4, 7], [8, 8]$로 총 3개입니다. 우리는 길이가 $N$이고...
-
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...
-
Solving Univariate Polynomial over Finite Field
서론 최근 finite field 위에서는 univariate polynomial을 빠르게 풀 수 있다는 소프트웨어 멤버십 노규민 님의 말씀을 들었습니다. 일반적인 합성수 modulus 위에서 Coppersmith method 등을 통해서 작은 값을 가지는 해를 구하는 방법에 대해서만 접해보았기 때문에, 이 방법에 흥미를 느끼고 한 번 정리해보게 되었습니다. 본론 찾아보니 해를 구하는 것은 Polynomial factorization과 밀접한 관련이 있어서, 유명한 Polynomial factorization 알고리즘인 Cantor–Zassenhaus algorithm을 알아보고, 이를 바탕으로 해를 구하는 방법에 대해서 알아보려고 합니다. Cantor–Zassenhaus algorithm Cantor–Zassenhaus algorithm의 메인 아이디어는 equal-degree factorization,...