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