-
BFV scheme에 대한 소개 - 4
Introduction 지금까지 BFV Scheme에 관한 설명글들을 썼고, 저번 글에서는 RNS form에서 처리하기 까다로운 연산 중에서 BFV decryption을 어떻게 처리하는지에 대해서 설명했습니다. 이번 글에서는 multiplication을 어떻게 처리하는지에 대해서 설명하도록 하겠습니다. Backgrounds 이번에 설명할 연산은 RNS module의 BFV scheme에서 multiplication 입니다. 얼핏 생각했을 때, decryption에서 rounding을 correction하는 법도 이미 구했고, Multiplication 역시 비슷하게 하면 되지 않을까? 라는 생각을 할 수 있습니다. NTT등을 사용하면 속도도 빠르게 나올 것입니다. 하지만, 그냥 곱하는 방법을 쓰면 문제가 있는데, 바로 Noise Growth가...
-
알고리즘 문제 접근 과정 12
알고리즘 문제 접근 과정 12 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 다만 기존과는 조금 달리, 이번에는 JOI 기출문제들 중 높은 난이도의 문제들을 위주로 이야기합니다. JOI 기출문제들은 좋은 문제들이 많음에도, 한글로 번역이 되어있지 않고 한글 풀이가 존재하지 않는 문제들이 있어, 이들 위주로 풀이를 작성하려고 합니다. 이번 문제들의 난이도는 기존 시리즈들과는 달리, 기출문제들 중 높은 번호의 문제들을 다루다보니 조금 어렵게 느껴질 수...
-
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).$...