개요 FFT는 이산적인 영역에서 하는 푸리에 변환인 DFT(Discrete Fourier Transform)을 분할정복 기법을 이용하여 $\Theta (n\,log\, n)$ 시간 내에 수행하는 알고리즘 입니다. 이를 보통 PS에서는 두 다항식의 곱셈을 $\Theta (n\,log\, n)$ 에 처리하기 위해 사용합니다. 이 글을 이해하기 위한 사전지식으로는 기초적인 프로그래밍 지식과 복소수 지수에 대한 이해가 필요합니다. DFT (Discrete Fourier Transform) 우선 DFT의 정의부터 살펴봅시다. 수열 $a_{0}, \,a_{1}, \,a_{2} , \,a_{3},\,...\, a_{n-1}$ 에 대하여, $\omega_{N} = e^{-2\pi i/N} $, $\hat{a}_{n} ..