티스토리 뷰
고속 푸리에 변환은 이산 푸리에 변환(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) (8) | 2014.07.25 |
포함-배제의 원리 (0) | 2014.07.20 |
Nim game (5) | 2013.07.29 |
-
장홍준 c(i) = 시그마 a(j)*b(i-j)인데 b(i-j)가 b(i)-j처럼 보이네요. 2014.08.21 10:23
-
전명우 감사합니다. 수정하였습니다. 2014.10.11 00:55 신고
-
익명 비밀댓글입니다 2016.09.28 09:29
-
gumgood fft코드 질문입니다.
a와 b의 차수가 2^n보다 작거나 같을 때, 결과인 res의 차수는 최대 2^(n+1)가 됩니다.
그러면 fa와 fb의 size를 2n으로 resize해야하는 것 아닌가요?? 2019.09.18 09:54 -
【ⓥⓘⓟ】Penta 동의합니다 2021.02.15 15:02
-
ㅇㅇ 43번 줄에서 max(sz(a), sz(b)) 가 아닌 sz(a) + sz(b) 가 되어야 합니다. 긁었는데도 이상하게 나와서 한참을 헤맸네요. ㅠㅠ 2021.07.29 20:33
-
전명우 gumgood 님이랑 ㅇㅇ 님이 말씀해주신 부분 코드에 반영했습니다. 감사합니다. 2021.12.08 22:47 신고
- Total
- 227,245
- Today
- 106
- Yesterday
- 92
- USACO
- Parametric Search
- BOI
- moore
- BOI 2009
- Dynamic Pramming
- Divide & Conquer
- idea
- Dijkstra
- TRIE
- Tree
- Splay Tree
- IOI2012
- Algorithm
- Boyer
- BOI 2001
- IOI2011
- dynamic programming
- IOI2014
- IOI2013
- Knuth Optimization
- ioi
- vote
- z-trening
- Boyer-Moore Majority Vote Algorithm
- Greedy Method
- Segment tree
- HackerRank
- majority
- optimization