-
다항식 나눗셈과 다중계산
서론 다항식 다중계산(Multipoint evaluation)은, $N$차 다항식 $f$에 대해, $Q$개의 원소 $x_1, x_2, \cdots, x_Q$ 를 $O(\max(N, Q)\log^2 \max(N, Q))$ 시간에 계산할 수 있도록 도와주는 도구이다. 이 Multipoint evaluation의 계산을 위해서는, 다항식의 빠른 곱셈, 다항식의 빠른 나눗셈을 알아야 한다. 이 글에서는 이를 계산 하는 빠른 방법을 알아본다. 다항식 곱셈 다항식의 빠른 곱셈에는 FFT를 사용한다. FFT란, $x_0, x_1, \cdots, x_{N=1}$ 을 $X_0, X_1, \cdots, X_{N=1}$으로 다음과 같은 규칙에 따라 바꾸는 변환이다. $X_k = \sum_{n=0}^{N-1} x_n \omega^{nk} \qquad...
-
행렬 분해(Matrix Decomposition)
행렬 분해(Matrix Decomposition) 행렬 분해(matrix decomposition)는 여러 특정 구조를 가진 행렬들의 곱으로 기존의 행렬을 나타내는 것을 의미합니다. 예를 들어, $ A = \begin{bmatrix} 1 & 2 & 3 \ 2 & 4 & 6 \ 3 & 6 & 9 \end{bmatrix}$ 와 같은 행렬을 생각해 봅시다. 이 경우 $ A $를 아래와 같이 $ 3 \times 1 $ 크기의 두 행렬과 $ 1 \times 1 $ 크기의 대각 행렬 을 통해 나타낼 수 있습니다. $...
-
Berlekamp-Massey 알고리즘의 이해와 응용
Berlekamp-Massey 알고리즘의 이해와 응용 Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지...
-
Discriminator Rejection Sampling
Generative Adversarial Networks(GANs)는 머신러닝 기술의 일종으로 생성자(generator)와 판별자(discriminator) 두 네트워크를 적대적으로 경쟁시켜 학습시키는 프레임워크를 말합니다. 보통 GANs에서는 학습이 완료되면 생성자 네트워크만 사용하고 판별자 네트워크는 버리게 됩니다. 하지만, 학습 이후에 여전히 생성자 네트워크가 실제 데이터 분포를 완벽히 묘사하지 못하고 판별자 네트워크가 이에 대해 중요한 정보를 가지고 있을 수도 있습니다. 그렇다면 학습 이후에도 판별자 네트워크를 활용하여 생성자 네트워크의 성능을 높일 수 있지 않을까요? Discriminator Rejection Sampling(DRS)은 ICLR 2019에 accept된 논문으로 GANs 학습 이후에 판별자(discriminator)를 이용하여 생성자(generator)의 성능을...
-
문제 출제를 위한 플랫폼 - Polygon 사용하기
Polygon이란? Polygon이란 Codeforces에서 제공하는 Competitive Programming Contest를 위한 문제 출제를 위한 플랫폼입니다. 출제를 위해 필요한 과정 - 데이터 제작, 검증, 솔루션 검증 등에 굉장히 유용한 기능들이 많으며 그 과정을 다른 사람과 공유하며 협업할 수도 있습니다. 폴리곤에서의 작업은 각 문제 단위로 동작합니다. 문제를 등록하는 방법부터 완성된 문제를 패키지로 다운받는 방법까지, 필요한 기능들을 간략히 확인하고 언제 어떤 메뉴를 사용해야 하는지 문제 출제 단계에 따라 익혀봅시다. 아, 그 전에 회원가입은 다들 하셔야겠죠? 문제 등록하기 폴리곤에 로그인하면 아래와 같은...