II-18 FFT의 복소수·단위원근·다항식 곱셈 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
FFT는 최적화 heuristic이 아니라 다항식을 coefficient 표현과 value 표현 사이에서 빠르게 변환하는 divide-and-conquer 알고리즘입니다.
두 긴 수열을 직접 모든 쌍으로 곱하지 않고 주파수 세계로 옮겨 점별 곱을 한 뒤 돌아오는 과정입니다.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. category(metaheuristic 아님), number system(complex 사용), primitive root, runtime pipeline 순으로 검사합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
FFT는 최적화 heuristic이 아니라 다항식을 coefficient 표현과 value 표현 사이에서 빠르게 변환하는 divide-and-conquer 알고리즘입니다.
이 문항에서 가장 먼저 붙잡을 문장은 'FFT는 실수만이 아니라 복소 단위원근(complex roots of unity)을 사용한다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- FFT는 실수만이 아니라 복소 단위원근(complex roots of unity)을 사용한다.
- category(metaheuristic 아님), number system(complex 사용), primitive root, runtime pipeline 순으로 검사합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, FFT는 실수만이 아니라 복소 단위원근(complex roots of unity)을 사용한다. 둘째, primitive n-th root ω=\(e^{2πi/n}\)e^(2πi/n)는 평가점을 제공한다.
셋째, \(\text{forward} \text{FFT}\to \text{pointwise} \text{multiplication}\to \text{inverse} \text{FFT}\)forward FFT→pointwise multiplication→inverse FFT가 polynomial product를 만든다. 넷째, 두 degree n-1 polynomial multiplication을 \(\Theta(n \log n)\)Θ(n log n)에 수행한다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- FFT는 실수만이 아니라 복소 단위원근(complex roots of unity)을 사용한다.
- primitive n-th root ω=\(e^{2πi/n}\)
e^(2πi/n)는 평가점을 제공한다. - \(\text{forward} \text{FFT}\to \text{pointwise} \text{multiplication}\to \text{inverse} \text{FFT}\)
forward FFT→pointwise multiplication→inverse FFT가 polynomial product를 만든다. - 두 degree n-1 polynomial multiplication을 \(\Theta(n \log n)\)
Θ(n log n)에 수행한다.
개념 3 · 강의 정의를 초보자 언어로 해체
계수 표현에서 다항식 곱셈을 하면 각 계수 조합을 모두 더하는 convolution이라 느리다. FFT의 핵심은 문제를 더 쉬운 표현으로 옮기는 것이다. 여러 x값에서 p(x), q(x)를 이미 알고 있으면 \(r(x)=p(x)q(x)\)r(x)=p(x)q(x)는 각 점에서 그냥 곱하면 된다. 어려운 부분은 많은 점에서 빠르게 값을 구하고 다시 계수로 돌아오는 일인데, 복소 원시 단위근을 고르면 even/odd 분할이 재사용되어 Divide-and-Conquer가 된다.
고속 푸리에 변환(FFT, Fast Fourier Transform)은 이산 푸리에 변환(DFT)을 \(\Theta(n \log n)\)Θ(n log n)에 계산하는 알고리즘이다. DFT는 계수 벡터 \(a_{0},...,a_{n-1}\)a₀,...,aₙ-1}를 원시 n차 단위근 ω_n의 거듭제곱에서 평가한 값 벡터로 바꾼다. 원시 m차 단위근(primitive m-th root of unity)은 ω_\(m^{m}=1\)mᵐ=1이고 \(1\le j<m\)1≤j<m에서는 ω_\(m^{j}\)m^j≠1을 만족하며, 복소수에서는 ω_\(m=\text{exp}(2\)m=exp(2πi/m)=cos(2π/m)+i sin(2π/m)로 쓸 수 있다. 점-값 표현(point-value representation)은 서로 다른 \(x_{j}\)xⱼ에 대한 쌍 \((x_{j},p(x_{j}))\)(xⱼ,p(xⱼ))로 다항식을 나타내는 방식이다.
수식으로 정확히 쓰기
핵심 규칙계수 표현 → \(\text{FFT} \to \)FFT →점별 곱셈\((\text{pointwise} \text{multiplication}) \to \)(pointwise multiplication) →역 \(\text{FFT}(\text{IFFT}) \to \)FFT(IFFT) →결과 계수 순서로 진행한다. 전체 시간은 \(\Theta(n \log n)\)Θ(n log n)+\(\Theta(n)\)Θ(n)+\(\Theta(n \log n)\)Θ(n log n)=\(\Theta(n \log n)\)Θ(n log n)이다.
이 절에서 꼭 기억할 것
- 복소수 i와 exp(2πi/n)
- 다항식 차수와 2n-1개의 점이 필요한 이유
- 분할 정복 점화식(Divide-and-Conquer recurrence)
- Θ 표기
개념 4 · 성립 조건·불변식·경계 사례
짝수·홀수 차수 분할은 \(p(x)=p_{\text{even}}(x^{2})+x p_{\text{odd}}(x^{2})\)p(x)=p(even)(x²)+x p(odd)(x²)로 쓴다. 원시근은 제곱했을 때 짝을 이루는 성질이 있어 절반 크기 부분문제가 같은 평가점을 재사용한다. 점별 곱셈(pointwise product)을 하려면 p와 q를 반드시 같은 x 좌표에서 평가해야 한다. 또한 차수가 최대 m-1인 다항식은 서로 다른 m개의 점-값 쌍으로 유일하게 결정된다.
차수가 n-1인 두 다항식의 곱은 차수가 최대 2n-2이므로 서로 다른 값이 최소 2n-1개 필요하다. 강의에서는 계산을 단순하게 하려고 2n개 점을 사용한다. n이 2의 거듭제곱이 아니면 0 계수를 덧붙이는 패딩(padding)을 사용할 수 있으며, 이는 점근 복잡도를 바꾸지 않는다. 원시근은 일반적으로 복소수이고, FFT는 휴리스틱 탐색이 아니라 정확한 대수 변환이다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
차수가 n-1인 두 다항식을 계수 합성곱으로 직접 곱하면 \(\Theta(n^{2})\)Θ(n²)이다. FFT 평가는 점화식 \(T(n)=2T(n/2)+\Theta(n)\)T(n)=2T(n/2)+Θ(n)에서 \(\Theta(n \log n)\)Θ(n log n)이 된다. 충분한 길이로 0을 채운 뒤 변환된 값을 점별로 곱하는 단계는 \(\Theta(n)\)Θ(n)이다. 역 FFT(IFFT)는 마지막에 n으로 나누는 단계까지 포함해 \(\Theta(n \log n)\)Θ(n log n)이므로, FFT 기반 다항식 곱셈 전체도 \(\Theta(n \log n)\)Θ(n log n)이다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 C, D입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: C, D
이 절에서 꼭 기억할 것
- A와 B는 강한 category/number-system 함정이고, C와 D는 primitive root와 runtime pipeline을 정확히 말한다.
- FFT가 'optimization heuristic'인지 묻는 문장은 지우고, 'real only'도 지운다. 남는 두 문장 primitive root와 \(\Theta(n \log n)\)
Θ(n log n)polynomial multiplication이 정답이다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
FFT의 복소수·단위원근·다항식 곱셈
FFT는 실수만이 아니라 복소 단위원근(complex roots of unity)을 사용한다. | primitive n-th root ω=\(e^{2πi/n}\)e^(2πi/n)는 평가점을 제공한다. | \(\text{forward} \text{FFT}\to \text{pointwise} \text{multiplication}\to \text{inverse} \text{FFT}\)forward FFT→pointwise multiplication→inverse FFT가 polynomial product를 만든다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
FFT에 관한 다음 네 문장 중 정확히 두 개를 고르시오.
핵심 규칙FFT의 복소수·단위원근·다항식 곱셈
핵심 도구를 종이에 꺼낸다
category(metaheuristic 아님), number system(complex 사용), primitive root, runtime pipeline 순으로 검사합니다.
핵심 규칙FFT는 실수만이 아니라 복소 단위원근(complex roots of unity)을 사용한다. | primitive n-th root ω=\(e^{2πi/n}\)
e^(2πi/n)는 평가점을 제공한다. | \(\text{forward} \text{FFT}\to \text{pointwise} \text{multiplication}\to \text{inverse} \text{FFT}\)forward FFT→pointwise multiplication→inverse FFT가 polynomial product를 만든다.선택지 A를 독립 판정한다
강의는 metaheuristics를 optimization problem용 상위 방법으로 따로 두고, FFT를 Divide & Conquer의 예로 제시한다. FFT는 DFT를 빠르게 계산하는 정확한 변환 알고리즘이지 해 공간을 탐색하는 heuristic가 아니다.
\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
강의의 primitive root 예시는 ω_\(m=\text{exp}(2\)
m=exp(2πi/m)=cos(2π/m)+i sin(2π/m)이다. i가 등장하므로 일반적인 FFT 설명은 복소수 단위근을 사용한다. 'ausschließlich'라는 강한 단어가 이 선택지를 깨뜨린다.\[선택지 B = 거짓\]선택지 B = 거짓선택지 C를 독립 판정한다
FFT가 arbitrary points가 아니라 원시 단위근의 거듭제곱을 택하는 이유는 even/odd split 후 \(x_{j}^2\)
xⱼ²값이 재사용되어 문제 크기가 반으로 줄기 때문이다. 강의와 Sheet 12 해설 모두 primitive roots를 이용한 재귀적 평가를 설명한다.\[선택지 C = 참\]선택지 C = 참선택지 D를 독립 판정한다
계수 표현에서 직접 convolution하면 \(\Theta(n^{2})\)
Θ(n²)이다. FFT로 점-값 표현으로 바꾸고 같은 x좌표에서 점별 곱셈을 \(\Theta(n)\)Θ(n)에 한 뒤 IFFT로 돌아오면 transform 두 번이 지배해서 전체 \(\Theta(n \log n)\)Θ(n log n)이 된다.\[선택지 D = 참\]선택지 D = 참정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 C, D입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = C, D\]검증된 정답 = C, D
2. 이 문제를 실제로 끝까지 풀기
FFT는 최적화 heuristic이 아니라 다항식을 coefficient 표현과 value 표현 사이에서 빠르게 변환하는 divide-and-conquer 알고리즘입니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) FFT는 실수만이 아니라 복소 단위원근(complex roots of unity)을 사용한다. (2) primitive n-th root ω=\(e^{2πi/n}\)e^(2πi/n)는 평가점을 제공한다. \((3) \text{forward} \text{FFT}\to \text{pointwise} \text{multiplication}\to \text{inverse} \text{FFT}\)(3) forward FFT→pointwise multiplication→inverse FFT가 polynomial product를 만든다. (4) 두 degree n-1 polynomial multiplication을 \(\Theta(n \log n)\)Θ(n log n)에 수행한다.
선택지 A는 거짓입니다. 강의는 metaheuristics를 optimization problem용 상위 방법으로 따로 두고, FFT를 Divide & Conquer의 예로 제시한다. FFT는 DFT를 빠르게 계산하는 정확한 변환 알고리즘이지 해 공간을 탐색하는 heuristic가 아니다. 가장 작은 확인 예는 같은 계수 벡터를 주면 FFT는 정해진 DFT 값을 계산한다. 후보 해를 개선하거나 local optimum을 찾는 과정이 없다.
선택지 B는 거짓입니다. 강의의 primitive root 예시는 ω_\(m=\text{exp}(2\)m=exp(2πi/m)=cos(2π/m)+i sin(2π/m)이다. i가 등장하므로 일반적인 FFT 설명은 복소수 단위근을 사용한다. 'ausschließlich'라는 강한 단어가 이 선택지를 깨뜨린다. 가장 작은 확인 예는 \(m=4\)m=4이면 ω_\(4=i\)4=i이고, i는 실수가 아니다.
선택지 C는 참입니다. FFT가 arbitrary points가 아니라 원시 단위근의 거듭제곱을 택하는 이유는 even/odd split 후 \(x_{j}^2\)xⱼ²값이 재사용되어 문제 크기가 반으로 줄기 때문이다. 강의와 Sheet 12 해설 모두 primitive roots를 이용한 재귀적 평가를 설명한다.
선택지 D는 참입니다. 계수 표현에서 직접 convolution하면 \(\Theta(n^{2})\)Θ(n²)이다. FFT로 점-값 표현으로 바꾸고 같은 x좌표에서 점별 곱셈을 \(\Theta(n)\)Θ(n)에 한 뒤 IFFT로 돌아오면 transform 두 번이 지배해서 전체 \(\Theta(n \log n)\)Θ(n log n)이 된다.
따라서 현재 문언에서 참으로 검증된 선택지는 C, D입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. category(metaheuristic 아님), number system(complex 사용), primitive root, runtime pipeline 순으로 검사합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
강의는 metaheuristics를 optimization problem용 상위 방법으로 따로 두고, FFT를 Divide & Conquer의 예로 제시한다. FFT는 DFT를 빠르게 계산하는 정확한 변환 알고리즘이지 해 공간을 탐색하는 heuristic가 아니다.
빠른 확인법: 같은 계수 벡터를 주면 FFT는 정해진 DFT 값을 계산한다. 후보 해를 개선하거나 local optimum을 찾는 과정이 없다.
-
B거짓
강의의 primitive root 예시는 ω_\(m=\text{exp}(2\)
m=exp(2πi/m)=cos(2π/m)+i sin(2π/m)이다. i가 등장하므로 일반적인 FFT 설명은 복소수 단위근을 사용한다. 'ausschließlich'라는 강한 단어가 이 선택지를 깨뜨린다.빠른 확인법: \(m=4\)
m=4이면 ω_\(4=i\)4=i이고, i는 실수가 아니다. -
C참 — 정답 후보
FFT가 arbitrary points가 아니라 원시 단위근의 거듭제곱을 택하는 이유는 even/odd split 후 \(x_{j}^2\)
xⱼ²값이 재사용되어 문제 크기가 반으로 줄기 때문이다. 강의와 Sheet 12 해설 모두 primitive roots를 이용한 재귀적 평가를 설명한다.빠른 확인법: FFT는 계산을 효율적으로 하기 위해 n-th primitive root of unity \(e^{2πi/n}\)
e²πi/n}을 사용한다. -
D참 — 정답 후보
계수 표현에서 직접 convolution하면 \(\Theta(n^{2})\)
Θ(n²)이다. FFT로 점-값 표현으로 바꾸고 같은 x좌표에서 점별 곱셈을 \(\Theta(n)\)Θ(n)에 한 뒤 IFFT로 돌아오면 transform 두 번이 지배해서 전체 \(\Theta(n \log n)\)Θ(n log n)이 된다.빠른 확인법: FFT는 차수 n-1인 두 다항식의 곱셈 시간을 \(\Theta(n^{2})\)
Θ(n²)에서 \(\Theta(n \log n)\)Θ(n log n)으로 줄인다.
4. 초보자가 가장 자주 틀리는 이유
- A와 B는 강한 category/number-system 함정이고, C와 D는 primitive root와 runtime pipeline을 정확히 말한다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
category(metaheuristic 아님), number system(complex 사용), primitive root, runtime pipeline 순으로 검사합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 C, D이다. 핵심 근거: FFT는 실수만이 아니라 복소 단위원근(complex roots of unity)을 사용한다. primitive n-th root ω=\(e^{2πi/n}\)e^(2πi/n)는 평가점을 제공한다. \(\text{forward} \text{FFT}\to \text{pointwise} \text{multiplication}\to \text{inverse} \text{FFT}\)forward FFT→pointwise multiplication→inverse FFT가 polynomial product를 만든다. 두 degree n-1 polynomial multiplication을 \(\Theta(n \log n)\)Θ(n log n)에 수행한다.
6. 스스로 이해했는지 확인
II-18의 주제를 한 문장으로 설명하면?
정답: FFT는 최적화 heuristic이 아니라 다항식을 coefficient 표현과 value 표현 사이에서 빠르게 변환하는 divide-and-conquer 알고리즘입니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: category(metaheuristic 아님), number system(complex 사용), primitive root, runtime pipeline 순으로 검사합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: FFT는 실수만이 아니라 복소 단위원근(complex roots of unity)을 사용한다.
핵심 사실 네 가지 중 두 번째는?
정답: primitive n-th root ω=\(e^{2πi/n}\)e^(2πi/n)는 평가점을 제공한다.
가장 위험한 함정은?
정답: A와 B는 강한 category/number-system 함정이고, C와 D는 primitive root와 runtime pipeline을 정확히 말한다.
정답 label은?
정답: C, D
FFT polynomial multiplication pipeline을 네 단계로 말하라.
정답: 계수 표현을 FFT로 점-값 표현으로 바꾸고, 같은 x좌표에서 점별로 곱한 뒤, IFFT로 계수 표현으로 되돌린다.
왜 primitive root of unity를 쓰는가.
정답: 원시 단위근의 거듭제곱을 평가점으로 쓰면 even/odd split 후 \(x^{2}\)x²값이 재사용되어 두 개의 half-size FFT로 내려갈 수 있다.
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-18
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section, question II-18
SoSe 2025 복기 문구, II부의 정확히 2개 선택 규칙, 배점, 네 FFT 선택지를 뒷받침한다.Vorlesung\07AdvancedDesigns.pdf· pp. 3-5
강의가 최적화 문제의 메타휴리스틱과 분할 정복을 구분하고 FFT를 분할 정복 방식의 푸리에 변환 예시로 소개한다.Vorlesung\07AdvancedDesigns.pdf· pp. 7-8
차수 n-1인 두 다항식의 계수를 직접 합성곱하면 \(\Theta(n^{2})\)Θ(n²)이 걸리지만, DFT/FFT 변환 뒤 점별 곱셈은 \(\Theta(n)\)Θ(n)이라는 내용을 뒷받침한다.Vorlesung\07AdvancedDesigns.pdf· pp. 13-18
FFT가 특수한 단위근, 특히 복소 원시근 exp(2πi/m)을 사용하고 짝수·홀수 차수 계수를 재귀적으로 나눈다는 내용을 뒷받침한다.