알고리즘 문제 풀이 노트: 트리 탐색, 선형 기반, 그리고 순열 최적화
CF1534H - 루트 탐색 최적화트리에서 두 노드 a, b를 찾기 위한 최소 질의 횟수를 분석한다. 루트 r를 고정했을 때, 각 노드 u에 대해 서브트리 내에서 탐색하는 최악의 비용 cost[u]를 정의한다.잎 노드의 경우 확인 비용은 1이다. 내부 노드에서는 자식들을 cost 기준 내림차순으로 정렬하여 탐색하며, i번째 자식을 탐색할 때의 비용은 cost[child_i] + i - 1이 된다. ...
6월 29일 01:05에 게시됨
다항식 연산과 고속 변환 알고리즘
다항식의 빠른 곱셈
두 다항식의 합성곱(convolution)을 계산할 때, 단순한 방법은 모든 항을 직접 곱하는 것으로 시간 복잡도는 $O(n^2)$이다. 하지만 $O(n \log n)$ 시간에 이를 수행할 수 있는 알고리즘이 존재하는데, 대표적으로 FFT(고속 푸리에 변환)와 NTT(수론적 변환)가 있다. 이들은 본질적으로 DFT(이산 푸리에 변환)와 IDFT(역 이산 푸리에 변환)를 효율적으로 ...
6월 18일 19:50에 게시됨