티스토리 뷰

공부

고속 푸리에 변환 (Fast Fourier Theorem, FFT)

전명우 2014. 7. 25. 18:57

고속 푸리에 변환은 이산 푸리에 변환(Discrete Fourier Transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘으로 알려져 있다. 이에 대한 이론적인 설명을 자세하게 하려는 목적은 아니다. FFT가 PS에 어떤 식으로 응용될 수 있는지에 대해서 아주 간단하게 소개하고자 한다.


PS 문제들을 풀다보면 FFT를 사용해야하는 경우를 대면하게 되는데, 이러한 문제들은 백날 생각해도 모르면 못 풀고, 조금을 생각하더라도 알면 푼다고 생각하기 때문에 꼭 알아둬야 되는 부분이라고 생각한다. 우선, PS에서 FFT가 사용되는 대표적인 예는 convolution를 $O(n \log_2 n)$만에 계산할 때이다.


Convolution이란, 여기에서 설명된 것 처럼 크기가 $n$인 배열 $a$, $b$가 있다고 했을 때, 아래와 같은 식으로 계산된 $c$를 convolution이라고 부른다. 이 배열들은 0-indexed 이다.


$c_i = \sum\limits^{i}_{j=0}{a_j \times b_{i-j}}$


일반적으로 $c$를 계산하는 시간복잡도는 $O(n^2)$이지만, FFT를 이용하면 계산하는 시간복잡도는 $O(n \log_2 n)$로 매우 빠르다. FFT에 대한 자세한 설명은 생략하고, $a$, $b$가 주어졌을 때 $c$를 계산하는 코드와 응용 문제들을 설명하겠다.


이러한 방법을 이해하기 위해서는 이론에 대해서 깊이 있는 공부를 해야하기 때문에 이해하지 않고 팀노트에 등록하는 것도 좋아보인다.



응용 문제 1) 부분 배열 곱


문제) 크기가 $N$인 정수 배열 $A$와 크기가 $M$인 정수 배열 $B$가 있다. ($M \leq N \leq 500,000$). 크기가 $M$인 $A$의 (연속한) 부분 배열 $C$가 있을 때, 함수 $f$의 정의는 다음과 같다. $f(C) = \sum\limits^{M}_{i=0}{B[i] \times C[i]}$. 이 때, $f(C)$가 최대가 되는 $C$를 찾아 $f(C)$ 값을 구하시오.


응용 문제 2) HackerRank w6 - Best spot


응용 문제 3) BOJ 1067번 이동

저작자표시

'공부' 카테고리의 다른 글

Suffix Array와 LCP  (14) 2014.08.14
Manacher's Algorithm  (0) 2014.08.13
중국인의 나머지 정리와 확장 유클리드 알고리즘  (0) 2014.07.25
고속 푸리에 변환 (Fast Fourier Theorem, FFT)  (6) 2014.07.25
포함-배제의 원리  (0) 2014.07.20
Nim game  (5) 2013.07.29
공유하기 링크
댓글
댓글쓰기 폼
1 ··· 75 76 77 78 79 80 81 82 83 ··· 130