-
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 $ 크기의 대각 행렬 을 통해 나타낼 수 있습니다. $...
-
Berlekamp-Massey 알고리즘의 이해와 응용
Berlekamp-Massey 알고리즘의 이해와 응용 Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지...