PS 이야기

Manacher's Algorithm은 문자열 내에서 회문(팰린드롬, palindrome)을 찾는 것과 관련된 알고리즘이며, 시간복잡도는 $O(N)$이다. (여기서 $N$은 문자열의 길이) 이 알고리즘은 문자열 $S$에 대해 아래와 같은 배열을 구할 수 있다.문자열 $S$의 길이, $|S| = N$과 같은 길이의 정수 배열 $A$$A$의 $i$번째 원소 $A[i]$는 $i$번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기 (회문의 길이가 5이면, 반지름은 2가 됨)즉, 부분 문자열 $S[i-A[i] ~ i+A[i]]$는 회문이며, $S[i-A[i]-1 ~ i+A[i]+1]$은 회문이 아니다. 예를 들어, "banana"라는 문자열 $S$에 대한 배열 $A$는 아래와 같다. $S$ b a n a n ..

1) 중국인의 나머지 정리 중국인의 나머지 정리는 PS를 하면서 간혹 등장한다. 답이 큰 경우 일반적으로 $M$으로 나눈 나머지를 출력하라고 한다. 하지만 이 $M$이 고정되어 있지 않고, 입력으로 $k$가지가 주어진다고 할 경우 $k$ 개 경우에 대해서 매번 다 계산하면 오래걸린다. 이럴 때 필요한 것이 바로 중국인의 나머지 정리다. 정리) 서로소인 $k$개의 자연수 $n_1, n_2, \dots, n_k$와 임의의 정수 $a_1, a_2, \dots, a_k$가 있을 때, 임의의 $i (1 \leq i \leq k)$에 대해 $x \equiv a_i (\mod n_i)$ 로 표현되는 변수 $x$의 연립 합동 방정식에 대해, 이 방정식이 성립하는 해 $x = a$가 항상 존재하며, $n_1 n_2 \d..

고속 푸리에 변환은 이산 푸리에 변환(Discrete Fourier Transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘으로 알려져 있다. 이에 대한 이론적인 설명을 자세하게 하려는 목적은 아니다. FFT가 PS에 어떤 식으로 응용될 수 있는지에 대해서 아주 간단하게 소개하고자 한다. PS 문제들을 풀다보면 FFT를 사용해야하는 경우를 대면하게 되는데, 이러한 문제들은 백날 생각해도 모르면 못 풀고, 조금을 생각하더라도 알면 푼다고 생각하기 때문에 꼭 알아둬야 되는 부분이라고 생각한다. 우선, PS에서 FFT가 사용되는 대표적인 예는 convolution를 $O(n \log_2 n)$만에 계산할 때이다. Convolution이란, 여기에서 설명된 것 처럼 크기가 $n$인 배열 $a..