-
번사이드 보조정리(Burnside Lemma)
서론 Burnside Lemma(번사이드 보조정리)는 Group action에서 나오는 정리입니다. 여기서 말하는 Group이란 대수학에서의 Group을 의미합니다. Competitive Programming에서 아주 가끔씩 경우의 수를 세는 문제에서 활용이 되나 객관적으로 나올 확률은 굉장히 낮다고 볼 수 있습니다. 이 글 자체는 Group Theory의 기초부터 차근차근 설명을 할 예정이지만 만약 Group Theory에 대해 이전에 전혀 공부를 한 적이 없다면 안타깝게도 이론적 배경을 이해하는 것이 불가능에 가까울 것입니다. 대신 이론적 배경을 이해하지 않고 하단의 실제 문제에서 Burnside Lemma를 사용하는 예시만을 익혀두어도 괜찮습니다. 배경...
-
Boost.Exception 소개
안녕하세요~ 오늘은 Boost.Exception 에 대해서 간단하게 소개해볼까 합니다. » 이 글을 좀 더 좋은 가독성으로 읽기 « Boost.Exception 이란? Boost.Exception 은 예외 계층을 설계하고 예외 핸들링을 수행할 때 도움을 주는 라이브러리입니다. 제가 Boost.Exception 을 사용하면서 얻을 수 있었던 이점은 다음과 같습니다. 예외가 발생한 시점의 소스파일 이름, 라인 넘버, 함수명을 예외 객체에 쉽고 편하게 담을 수 있습니다. throw std::exception() 대신에 BOOST_THROW_EXCEPTION(std::exception()) 을 사용하면 std::exception 을 wrapping 하는 예외 객체가 만들어지고 그 안에 소스파일 이름, 라인 넘버,...
-
Python의 큰 정수 표현법 1
개요 대부분의 프로그래밍 언어, 특히 거의 모든 저레벨 언어에는 정수형 크기에 제한이 있습니다. 대체로 바이트 단위로 끊어서 1바이트, 2바이트, 4바이트, 8바이트 정도의 정수형들을 사용할 수 있고, 언어와 컴파일러에 따라서는 16바이트 정수형이 제공되기도 합니다. 이와 같은 제한은 현대 프로세서들의 연산 능력을 고려하여 디자인된 것이라고 할 수 있습니다. 최근까지도 32비트/64비트 프로세서들이 주류를 이루고 있고, 이는 곧 프로세서가 연산을 수행하는 레지스터의 크기가 4/8바이트 정도이며 한 번의 연산 단위가 될 수 있다는 뜻이 됩니다. 따라서 이 크기에 맞추어 자료형을...
-
다항식 나눗셈과 다중계산
서론 다항식 다중계산(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 $ 크기의 대각 행렬 을 통해 나타낼 수 있습니다. $...