-
Relaxed Convolution (2)
개요 이전에 작성한 글에서는 Relaxed Convolution의 개념과 성질, 구현 방법에 대해서 다루었습니다. 이 글에서는 Relaxed Convolution을 Problem Solving에 활용하는 방법을 다룹니다. 연습 문제 AtCoder Beginner Contest 213 H. Stroll 문제 정점이 $N$개이고 간선이 매우 많은 무방향 그래프가 주어집니다. 간선 집합은 다음과 같은 방식으로 정의됩니다. $0 \leq i < M, 1 \leq d \leq T$를 만족하는 모든 $(i,d)$ 쌍에 대해, 두 정점 쌍 $(a_i, b_i)$를 잇는 길이가 $d$인 간선이 $p_{i,d}$개 존재합니다. 이 그래프의 $1$번 정점에서 출발해서...
-
CDQ Divide and Conquer, Relaxed Convolution
개요 CDQ Divide and Conquer는 중국 프로그래머 CDQ의 이름을 딴 분할정복 기법의 일종입니다. 딱히 이름이 붙을 정도로 거창한 기법은 아니지만, 이후에 다룰 Relaxed Convolution의 이해를 돕기 위해 간단하게 소개하겠습니다. Relaxed Convolution은 CDQ Divide and Conquer를 사용해서 Convolution을 온라인으로 처리하는 알고리즘으로, Online Convolution, Online FFT, Relaxed Multiplication, Divide and Conquer FFT 등의 다양한 이름으로 불리기도 합니다. 이 글에서는 Relaxed Convolution이라는 용어를 일관적으로 사용하겠습니다. 이 글은 FFT의 작동 원리를 이해하지 않고 빠른 다항식 곱셈 라이브러리를 blackbox로 사용하더라도...
-
구간 최장 증가 부분 수열 쿼리 (Part 2)
Chapter 4. $\boxdot$ 연산자의 빠른 구현 현재 우리의 알고리즘이 $O(N^5)$ 인 이유는 다음과 같다: $\boxdot$ 연산자가 $O(N^3)$ 에 구현됨 $\boxdot$ 연산자를 $O(N^2)$ 번 호출함 잠시 $\boxdot$ 연산자의 실제 이름을 짚고 넘어가자면, 논문에서는 위 연산자가 unit-Monge matrix-matrix distance multiplication 라는 이름으로 소개되었다. Part 1에서는 괜히 글이 어렵다는 인상을 줄 것 같아서 의도적으로 언급하지 않은 이름이다. 이제부터는 (순열의) unit-Monge 곱 이라고 부르거나 그냥 앞과 같이 $\boxdot$ 이라고 부른다. $\boxdot$ 연산자를 어떻게 $O(N \log N)$ 에 계산하는지 살펴보자....
-
구간 최장 증가 부분 수열 쿼리 (Part 1)
이번 글에서는 다음과 같은 쿼리를 수행하는 자료 구조에 대해 다룬다: 길이 $N$ 의 수열 $A$ 와 $Q$ 개의 쿼리 $1 \le i \le j \le N$ 가 주어질 때, $A[i], A[i + 1], \ldots, A[j]$ 의 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 를 계산하라. LIS 문제의 경우 동적 계획법으로 해결할 수 있는 가장 기초적인 문제 중 하나로, 수학적으로 여러 의미를 가지기 때문에 변형된 문제들이 다방면으로 연구되고 있다. 위와 같은 쿼리 문제는 다들 자료...
-
Graph Distance Labeling Problem
Introduction 정점이 $N$개인 무방향 무가중치 그래프가 주어졌을 때, 아무 두 정점 $u, v$ 사이의 최단 경로의 길이를 질문(query)할 수 있는 자료구조를 만들고 싶다고 합시다. 일반적인 상황이라면 이 질문에 대한 답은 매우 간단합니다. Floyd-Warshall 알고리즘 등으로 정점의 최단 경로를 크기 $N \times N$ 배열 (lookup table) $d$에 저장하고, $d(u, v)$를 $O(1)$ 시간에 찾아주면 됩니다. 하지만 어떤 이유로 Lookup table $d$를 유지할 수 없다고 합시다. query time에 $d$를 접근하는 비용이 너무 큰 상황이나, 분산 네트워크 환경에서 중앙화된...
-
Minimum $s - t$ cut of a planar undirected graph in $O(n \log^2 n)$ time
Minimum $s - t$ cut of a planar undirected graph in $O(n \log^2 n)$ time 간선에 가중치가 있는 그래프가 주어졌을 때, 최소 $s - t$ 컷은 두 정점 $s, t$ 가 연결되지 않게 하기 위해 지워야 하는 간선 집합의 최소 가중치 합을 뜻한다. Min-cut Max-flow theorem에 의해서, 최소 $s - t$ 컷은 최대 유량 알고리즘을 사용하여 다항 시간에 구할 수 있음이 잘 알려져 있다. 그래프의 최소 컷과 최대 유량의 중요성에 대해서는 이미 여러 번의 SW...