다항식 기초: FFT와 NTT
이 문서는 다항식 연산의 기본 개념을 다룹니다. 특히 빠른 푸리에 변환(FFT)과 빠른 수론 변환(NTT)을 중심으로 설명합니다.
FFT: 다항식 곱셈의 효율적 구현
FFT는 다항식을 단위근에서의 점값 표현으로 변환하는 과정을 가속화하는 알고리즘입니다. 주어진 다항식 F(x) = Σ aᵢxⁱ를 ωₙ⁰, ωₙ¹, ..., ωₙ^(n-1)에서 평가하는 과정을 분할 정복 방식으로 수행합니다.
핵심 ...
7월 31일 20:45에 게시됨
HEOI2016/TJOI2016 알고리즘 문제 해설
[HEOI2016/TJOI2016] 트리
이 문제는 트리에서 노드를 표시하거나, 특정 노드로부터 가장 가까운 조상 중 표시된 노드를 찾는 쿼리를 처리해야 한다. 이를 효율적으로 해결하기 위해 경로 분할(Heavy-Light Decomposition) 기법을 사용한다. 각 경로 체인의 맨 위에 있는 표시된 노드를 관리하고, 세트(set)를 이용해 체인 내 위치를 추적한다. 쿼리는 부모 방향으로 이동 ...
7월 14일 19:41에 게시됨
다항식 연산 알고리즘 정리
다항식 곱셈
두 다항식 F(x)와 G(x)가 주어졌을 때, H(x) = F(x)G(x)를 계산한다.
NTT를 활용해 점값 표현으로 변환한 후 점별 곱셈을 수행하고, 역변환으로 결과를 얻는다. 시간 복잡도는 O(n log n)이다.
void poly_multiply() {
read(n, m);
FOR(i, 0, n) read(f[i]);
FOR(i, 0, m) read(g[i]);
int sz = 1, bit = 0;
while(sz > 1) | ((i & 1 ...
6월 29일 22:19에 게시됨
다항식 연산과 고속 변환 알고리즘
다항식의 빠른 곱셈
두 다항식의 합성곱(convolution)을 계산할 때, 단순한 방법은 모든 항을 직접 곱하는 것으로 시간 복잡도는 $O(n^2)$이다. 하지만 $O(n \log n)$ 시간에 이를 수행할 수 있는 알고리즘이 존재하는데, 대표적으로 FFT(고속 푸리에 변환)와 NTT(수론적 변환)가 있다. 이들은 본질적으로 DFT(이산 푸리에 변환)와 IDFT(역 이산 푸리에 변환)를 효율적으로 ...
6월 18일 19:50에 게시됨