728x90 반응형 FFT1 FFT(Faster Fourier Transformation)에 대해서 https://codeforces.com/blog/entry/43499 https://codeforces.com/blog/entry/43499 codeforces.com ^영어가 된다면 이것부터 보는 것을 과감히 추천^ 이번에 다수의 FFT를 이용한 문제 풀이를 하면서 이 알고리즘을 너무 어렵지 않은 선에서 간략히 정리해보고자 한다. 우선, "Fast"하지 않은, 그냥 기본적인 푸리에 변환을 어떤 경우에 이용할 수 있는지를 설명하는 것이 좋을 것 같다. 위키피디아에 따르면 푸리에 변환은 "시간이나 공간에 대한 함수를 시간 또는 공간 주파수 성분으로 분해하는 변환"을 말한다. 이렇게 말하면 감이 잘 잡히지 않을 수 있는데, 어떤 함수를 그 함수를 정확히 나타낼 수 있을 만큼의 "점"들로 변환하는 것을 말한.. 2022. 9. 24. 이전 1 다음 728x90 반응형