알고리즘3 고속 푸리에 변환, 이론부터 구현까지 1. 구현하기 전에 필요한 지식 고속 푸리에 변환(Fast Fourier Transform; FFT)은 어떤 벡터의 이산 푸리에 변환을 \( O(n \log n) \) 안에 구할 수 있게 해주는 쉬우면서도 강력한 알고리즘이다. 푸리에 변환이라고 하니 굉장히 생소해 보이고, 신호 처리나 미분방정식 푸는 데 외에는 쓸데가 없어 보이지만, 사실 이걸 갖고 상당히 많은 일을 할 수가 있다. 예를 들자면 차수가 n인 두 다항식을 \( O(n \log n) \)에 곱한다. (가장 직관적인 방법으로 계산하면 \( O(n^2) \)이 나오게 된다.) 크기가 \( 10^n \) 정도인 두 자연수를 \( O(n \log n) \)에 곱한다. (마찬가지로 직관적으로 곱하면 \( O(n^2) \)이다.) 자연수 집합의 두 부.. 2023. 1. 2. [백준 18542] Permutant (Ruby III) 풀이 https://www.acmicpc.net/problem/18542 18542번: Permutant Consider an \(n \times n\) matrix \(A\). Let us denote element in \(i\)-th row and \(j\)-th column as \(A_j^{(i)}\). You are given a sequence \(a_1, \dots , a_n\) and a permutation \(π_1, \dots , π_n\) such that the first row is formed by sequence \(a_k www.acmicpc.net 먼저 주어진 Permutation는 Linear Transform의 일종임을 파악해야 한다. 예를 들어, Permutation {.. 2022. 8. 4. [C++] 선분 교차 판정 선분 교차 판정이란 말 그대로 두 선분이 교차하는지 아닌지 판정하는 것이다. 선분 교차 판정을 효율적으로 하기 위해서는 CCW(또는 signed area)에 대한 지식이 필요하다. CCW(또는 signed area)란? 세 점 A, B, C에 대하여 선분 BC가 AB에 대하여 시계 방향으로 휘어져 있는지 반시계 방향으로 휘어져 있는지 판정하는 것으로, 2차원에서 determinant의 개념을 응용하는 기술이다. 두 2차원 벡터 u, v의 determinant는 2가지 정보를 담고 있다. 그 절댓값은 두 벡터 u, v가 생성하는 평행사변형의 넓이를 알려주고, 그 부호는 v가 u에 대하여 시계 방향으로 휘어져 있는지 반시계 방향으로 휘어져 있는지를 알려준다(+: 반시계, -: 시계). PS계에서는 CCW라는.. 2022. 8. 4. 이전 1 다음
