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

고속 푸리에 변환은 이산 푸리에 변환(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$를 계산하는 코드와 응용 문제들을 설명하겠다.

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

#define _USE_MATH_DEFINES #include <math.h> #include <complex> #include <vector> #include <algorithm> using namespace std; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef complex<double> base; void fft(vector <base> &a, bool invert) { int n = sz(a); for (int i=1,j=0;i<n;i++){ int bit = n >> 1; for (;j>=bit;bit>>=1) j -= bit; j += bit; if (i < j) swap(a[i],a[j]); } for (int len=2;len<=n;len<<=1){ double ang = 2*M_PI/len*(invert?-1:1); base wlen(cos(ang),sin(ang)); for (int i=0;i<n;i+=len){ base w(1); for (int j=0;j<len/2;j++){ base u = a[i+j], v = a[i+j+len/2]*w; a[i+j] = u+v; a[i+j+len/2] = u-v; w *= wlen; } } } if (invert){ for (int i=0;i<n;i++) a[i] /= n; } } void multiply(const vector<int> &a,const vector<int> &b,vector<int> &res) { vector <base> fa(all(a)), fb(all(b)); int n = 1; while (n < max(sz(a),sz(b))) n <<= 1; fa.resize(n); fb.resize(n); fft(fa,false); fft(fb,false); for (int i=0;i<n;i++) fa[i] *= fb[i]; fft(fa,true); res.resize(n); for (int i=0;i<n;i++) res[i] = int(fa[i].real()+(fa[i].real()>0?0.5:-0.5)); }

응용 문제 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)  (7)	2014.07.25
포함-배제의 원리  (0)	2014.07.20
Nim game  (5)	2013.07.29