FFT

핵심 아이디어

FFT는 푸리에 변환이나 다항식 평가를 빠르게 계산하기 위한 알고리즘입니다. 전체 계산을 작은 구조로 나누어 반복함으로써 계산량을 크게 줄입니다.

이 블로그에서의 역할

Mathbong에서는 공통수학1 부록에서 다항식과 합성곱이 신호처리, 이미지 압축, 통신 기술로 어떻게 이어지는지 보여 줄 때 FFT를 소개합니다. 수학적 구조가 알고리즘 성능을 바꾸는 대표 사례입니다.