FFT 알고리즘 클래스

2022-01-06T15:00:00Z

  • 주제
    FFT Algorithm을 주제로 배경지식이 되는 수학 이론을 탐구하고 이를 C++과 Python 코드로 구현하였습니다. 이를 토대로 <백준> 온라인저지에서 FFT 응용문제를 풀이하였습니다.

  • 팀원
    박지혁, 진범진, 정훈규

  • 내용

  1. 수학
    복소 공간, DFT, Convolution, FFT, Butterfly Operation을 학습하였습니다.
    다항식의 곱셈을 Discrete Convolution의 성질을 이용하여 O(n logn) 시간 안에 해결하는 Convolution의 응용을 학습하였습니다.
    FFT의 구현법 2가지를 알아보았습니다. (재귀함수, 반복문)

  2. 알고리즘
    <백준> 온라인저지 13277, 1067, 10531, 14958번을 풀이하였습니다.