목록2026/03/06 (1)
Elevation
고속 푸리에 변환(FFT) for ps
고속 푸리에 변환은 합성곱(convolution)을 빠르게 처리하기 위해 사용되는 알고리즘이다. $$ F \ast G = \sum_k F[k] G[t-k] $$ 합성곱은 이산 공간에서 위와 같이 정의된다. 변수의 합을 $t$로 고정시켜 놓고, $k$를 움직여 가며 누적한 결과라고 이해하면 되겠다. 가장 대표적인 상황은 두 다항식을 곱했을 때, 차수가 $t$인 항의 계수를 구하는 경우일 것이다. 합성곱을 정의 그대로 구현하면 당연히 $O(N^2)$이 소요되겠지만, fft를 사용하면 $O(N \log N)$만에 합성곱을 구할 수 있다. 이산 푸리에 변환FFT를 이용해 합성곱을 구하는 과정은 다음과 같이 진행된다. 길이 $N$인 배열 $F, G$ 각각을 먼저 푸리에 변환($F_f , G_f$)한다. 변환 시..
ps/기타
2026. 3. 6. 20:40