-
Randomized Algorithm의 시간 복잡도 분석
Introduction 우리가 PS에 대해 배우면서 학습하는 대부분의 알고리즘은, 확률에 의존하지 않는다. 해당 알고리즘의 로직을 올바르게 구현했을 때에는 항상 정해진 시간 복잡도로 정답을 낸다. 현대 연구되는 많은 알고리즘은 그렇지 않다. 알고리즘은 확률적으로 오답을 낼 수도 있고, 정답과 적절히 가까운 근삿값만을 계산할 수도 있다. 또는 알고리즘의 수행 시간이 확률적으로 들쑥날쑥할 수 있다. 이러한 알고리즘의 가장 간단한 예시로는 피벗을 무작위로 잡는 퀵 소트 알고리즘이 있다. 무작위 알고리즘 (Randomized algorithm) 가운데, 항상 정답을 내는 것이 보장된 알고리즘을 Las Vegas...
-
Piece Table
서론 텍스트 에디터는 하나의 문자열을 조작하는 것을 매우 빠르게 하는 자료구조가 필요합니다. 길이가 $n$인 문자열 $s$에 대해서 다음과 같은 기능들이 있어야 합니다: $s = s[0..i] + s[j..n], 0 \le i < j \le n$, 즉, $i$ ~ $j$까지의 문자들을 지운다 $s = s[0..i] + t + s[i..n]$, 즉, $i$ 위치에 문자열 t를 넣는다 $s[i..j]$, 즉, $i$부터 $j$까지의 문자열을 빠르게 구한다 텍스트 에디터에는 문자열 찾기, 줄 번호 등 여러 기능이 있어야 하지만 우선 가장 중요한 기능은...
-
Poly-logarithmic Randomized Bellman-Ford (1/2)
Introduction Single-Source Shortest Path (SSSP) 문제는 알고리즘 입문에서부터 다루는 아주 기초적이고, 또 중요한 문제입니다. 엄밀하게 적자면, $n$개의 정점과 $m$개의 가중치 있는 단방향 간선을 갖는 그래프 $G$와 시작 정점 $s$가 주어질 때, 모든 점 $i$에 대해 $s$에서 $i$로 가는 최단 경로의 길이 $\mathrm{dist}(s, i)$ 를 묻는 문제입니다. 일반적으로 가중치가 모두 양수인 경우에 사용할 수 있는 Dijkstra’s algorithm과 가중치의 값과 무관하게 사용할 수 있는 Bellman-Ford algorithm이 가장 유명합니다. 각각의 시간 복잡도는 $\mathcal{T}[\text{Dijkstra}]$: Practical한 선에서 $O(m \log n).$...
-
구간 최장 증가 부분 수열 쿼리 (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)$ 에 계산하는지 살펴보자....
-
Introduction to Hardness Proofs and 3SUM Conjecture
Introduction to Hardness Proofs and 3SUM Conjecture Introduction 어떤 문제를 푸는 가능한 한 빠른 알고리즘을 찾아내는 것은 이론전산학 분야의 주된 관심사 중 하나입니다. 어떠한 문제든 우리가 원하는 만큼 빠른 알고리즘이 존재한다면 좋겠지만, 아쉽게도 이는 사실이 아닙니다. 예를 들어, $N$개의 정수를 크기 순으로 정렬하는 데에는 적어도 $\mathcal{O}(N\log N)$ 시간이 필요하다는 사실이 알려져 있습니다. 그렇다면 질문을 바꿔서, 어떤 문제를 해결하는 알고리즘의 시간 복잡도의 하한을 알 수는 있을까요? 이를 다른 말로 해당 문제의 hardness을 알아낸다고 말하는데, 이 역시도...