티스토리 뷰
고속 푸리에 변환은 이산 푸리에 변환(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$를 계산하는 코드와 응용 문제들을 설명하겠다.
이러한 방법을 이해하기 위해서는 이론에 대해서 깊이 있는 공부를 해야하기 때문에 이해하지 않고 팀노트에 등록하는 것도 좋아보인다.
FFT 코드
응용 문제 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 (11) | 2014.08.14 |
|---|---|
| Manacher's Algorithm (0) | 2014.08.13 |
| 중국인의 나머지 정리와 확장 유클리드 알고리즘 (0) | 2014.07.25 |
| 고속 푸리에 변환 (Fast Fourier Theorem, FFT) (4) | 2014.07.25 |
| 포함-배제의 원리 (0) | 2014.07.20 |
| Nim game (1) | 2013.07.29 |
- Total
- 123,708
- Today
- 4
- Yesterday
- 87
- vote
- dynamic programming
- z-trening
- IOI2014
- BOI 2009
- Greedy Method
- Algorithm
- Splay Tree
- Parametric Search
- BOI 2001
- Divide & Conquer
- IOI2012
- Tree
- BOI
- Dynamic Pramming
- IOI2011
- Knuth Optimization
- IOI2013
- majority
- USACO
- moore
- Boyer-Moore Majority Vote Algorithm
- optimization
- ioi
- idea
- TRIE
- Boyer
- Dijkstra
- HackerRank
- Segment tree