지금까지 고속푸리에변환(이하 FFT)의 원리를 잘 모르고 썼는데 오늘 각잡고 공부해서 깨달았다.
아직 완벽히 이해한건 아닌것 같지만 잊어버리기 전에 남겨놓고자 한다.
(쓰다보니 길어져서 파트를 나누었다. part1은 필요한 지식, part2에 FFT 원리에 대해 포스팅한다.)
감사한 곳
https://codeforces.com/blog/entry/43499
FFT는 다항식을 빠르게 계산하는 알고리즘이다.
$A(x) = \sum_{i=0}^{n-1} a_ix^i, B(x) = \sum_{i=0}^{n-1} b_ix^i$일 때 $C(x)=A(x)B(x)$를 빠르게 구하는 알고리즘이다.
그냥 단순 알고리즘으로 구한다면 $O(n^2)$이 걸릴 것인데 FFT를 이용하면 $O(n \log n)$에 구할 수 있다.
이제 천천히 알아보자.
Point form & Coefficient form
프로그래밍 할 때 다항식을 나타내는데 우리는 주로 배열을 사용한다.
예를들어 $A(x) = x^2+2x+5$라면 $A = [1,2,5]$로 사용한다.
이렇게 나타내는 방법을 Coefficient form이라고 한다.
반면 미지수가 $n$개인 연립 방정식에서 식이 $n$개가 주어지면 유일한 해가 존재하는 것이 알려져있다.
$3x+2y=5$
$2x+5y=7$
은 식이 2개이고 미지수가 2개이므로 유일한 해가 존재한다.
이를 다항식에 적용해보자.
$A(x) = a_0+a_1x+a_2x^2+\dots+a_{n-1}x^{n-1}$에서 $a_0, a_1, \dots, a_{n-1}$을 찾아야 한다.
미지수가 $n$개니까 $(x_0, y_0), (x_1, y_1), \dots, (x_{n-1},y_{n-1})$을 알고 있다면 계수들을 찾을 수 있을 것이다.
$(x_0, y_0), (x_1, y_1), \dots, (x_{n-1},y_{n-1})$ 이런 식으로 나타내는 방법이 Point form이다.
Coefficient form -> Point form
이는 단순히 $x = 0, 1, \dots, n-1$을 대입하면 $\{(0, A(0)), (1, A(1)), \dots, (n-1, A(n-1))\}$인 Point form 을 얻을 수 있다.
$n$개의 점을 구하는데 $O(n)$이걸리기 때문에 시간 복잡도는 $O(n^2)$이 된다. (이를 FFT로 단축시킬 것이다.)
Point form -> Coefficient form
$A = {(x_0, y_0), (x_1, y_1), \dots, (x_{n-1},y_{n-1})}$가 주어져 있다고 하자.
$\begin{pmatrix} 1 & x_0 & x_0^2 & \dots & x_0^{n-1} \\ 1 & x_1 & x_1^2 & \dots & x_1^{n-1} \\ \dots & \dots &\dots &\dots &\dots \\ 1 & x_{n-1} & x_{n-1}^2 & \dots & x_{n-1}^{n-1} \end{pmatrix} ^ {-1} \begin{pmatrix} y_0 \\ y_1 \\ \dots \\ y_{n-1} \end{pmatrix} = \begin{pmatrix} a_0 \\ a_1 \\ \dots \\ a_{n-1} \end{pmatrix}$
이러한 연립방정식을 해결하여 구할 수 있다.($O(n^2)$)
다항식을 곱하는 과정
1. $A$, $B$를 point form 으로 변환 (DFT : $O(n^2)$, FFT : $O(n \log n)$)
2. $C = AB$를 수행 ($O(n)$)
3. point form 인 $C$를 coefficent form으로 되돌리기 (IDFT : $O(n^2)$, IFFT : $O(n \log n)$)
이제 FFT를 알아보려고 하는데 그 전에 여러가지 수학적 사실을 알아야 한다.
한번 가볍게 짚고 넘어가자.
복소수
$i^2 = -1$인 $i$를 허수라고 하고 이를 포함한 수 체계를 복소수라고 한다.
복소수는 $z = a+bi (a \in \mathbb{R}, b \in \mathbb{R})$로 나타낸다.
오일러 공식
$e^{xi} = \cos x + i \sin x$
$z = re^{xi}$로 하여 모든 복소수를 나타낼 수 있다.
De Moivre 공식
$|z| = 1$이라고 하자.(즉, $r = 1$)
$(\cos x+i \sin x)^n = \cos (nx) + i \sin (nx)$이다.
proof)
$z^n = (\cos x+i \sin x)^n= e^{xin} = \cos (nx) + i \sin (nx)$
단위 근
자연수 $n$에 대해 $z^n = 1$인 $z$를 단위 근이라고 한다.
단위 근은 $n$개 존재하고 각각 $w_1, w_2, \dots, w_n$라고 하면 $w_j^n = 1$이다.
De Moivre 공식에 의해 $w_j^n = \cos (nx) + i \sin (nx) $
$w_j^n=1$이려면 $nx = 2 \pi k$여야 한다. (삼각함수의 주기성, $k \in \mathbb{Z}$)
그러한 $x = \frac{2 \pi k}{n}$이다.
따라서 단위근은 $ w_j = e^{xi} = e^{i \frac{2 \pi j}{n}} $가 된다.($ j \in \{0,1,\dots,n-1 \} $)
앞으로 표기할 때 $w_n^k = e^{\frac{2 \pi k}{n} i}$로 표기할 것이다.
Lemma 1
$n \ge 0, k \ge 0, d \ge 0$ 일 때 $w_{dn}^{dk} = w_n^k$이다.
proof)
$w_{dn}^{dk} = e^{\frac{2 \pi dk}{dn}i} = e^{\frac{2 \pi k}{n}i} = w_n^k$
Lemma 2
$n > 0$이고 짝수라면 $w_n^{\frac{n}{2}} = w_2 = -1$
proof)
$w_n^{\frac{n}{2}} = e^{\frac{2 \pi}{n}i \frac{n}{2}} = e^{\pi i} = -1$
Lemma 3
$n>0$이고 짝수라면 $(w_n^k)^2 = w_{\frac{n}{2}}^k$이다. (proofed by lemma 1)
Lemma 4
$n \ge 0, k \ge 0$이면 $w_n^{k+\frac{n}{2}} = -w_n^k$
proof)
$w_n^{k+\frac{n}{2}} = e^{\frac{2 \pi}{n} i (k+\frac{n}{2})} = e^{\frac{2 \pi i}{n} k + \pi i} = e^{\frac{2 \pi i}{n}{k}} \times (-1) = -w_n^k$
이제 다음 파트에서 FFT를 해보도록 한다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] UCPC 2022 예선 후기 (0) | 2022.07.04 |
---|---|
[알고리즘] 파이썬 dict, C++ map/unordered_map (0) | 2022.06.15 |
[알고리즘] Codeforces Round #784 (Div. 4) (0) | 2022.04.22 |
[알고리즘] Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics) (0) | 2022.03.09 |
[알고리즘] Codeforces Round #774 (Div. 2) (0) | 2022.03.05 |