-
Formal Power Series와 Operation의 빠른 계산 방법
Introduction Polynomial Ring Field $\mathbb{F}$에 대해 Polynomial Ring $\mathbb{F}[x]$는 다항식(polynomial)들의 집합으로 정의되며, 다항식들은 각 계수 $p_i$가 $\mathbb{F}$의 원소인 $p = p_0 + p_1x + … + p_mx^m$ 꼴로 표현됩니다. 여기에서 Ring이란 간단히 말해서 덧셈과 곱셈이 정의되어 있고 해당 연산들에 대해 결합법칙이 성립하고 항등원이 정의되어 있으며 덧셈에 대해서는 교환법칙이 성립하는 집합을 말합니다. Field는 여기에 0을 제외한 모든 원소에 대해 곱셈에 대한 역원이 존재하는 경우입니다. Polynomial Ring 같은 경우는 다항식의 곱셈과 덧셈으로 자연스럽게 정의됨을 알 수 있습니다....
-
와일드카드 문자열 매칭
서론 문자열 매칭 알고리즘은, 문자열 $S$와 $T$가 주어졌을 때, $S$의 부분문자열(substring) 중에 $T$가 어느 위치에 등장하는지 찾는데 사용하는 알고리즘이다. 우리는 이 문자열 매칭 알고리즘에 와일드카드 문자, 즉, 어떤 문자에도 대응 될 수 있는 ? 문자가 들어갔을 때 어떤 식으로 문제를 해결해야 하는지 알아본다. ? 문자가 들어가지 않았을 때 문자열 매칭을 하는 법에 대해서는, KMP 알고리즘과 Aho-Corasick 알고리즘 문서에 잘 설명이 되어 있으니, 참고하면 된다. 문제 우리가 풀고 싶은 문제는 다음과 같다. 문자열 길이 $N$의 문자열...
-
N! mod P 의 빠른 계산
서론 $N!$ 은 1이상 $N$ 이하의 모든 정수를 곱한 수 이다. 이 $N!$는 다양한 조합론적 상황에서 많이 사용된다. 이 $N!$을 특정한 소수 $P$로 나눈 나머지를 빠르게 ($O(\sqrt{N} \log{N})$ 시간에) 계산 하는 방법에 대해서 알아본다. Naive 팩토리얼을 구하는 가장 쉬운 방법은 모든 1이상 $N$ 이하의 수를 곱해서 $P$ 로 나누는 것이다. $ab$를 $P$로 나눈 나머지와 $(a \bmod P)(b \bmod P) \bmod P$ 가 같다는 것을 이용하면, 사이에 나오는 숫자를 항상 $P^2$ 이하로 유지하면서 쉽게 구할 수...