이론 (4) 썸네일형 리스트형 PS에서 쓰는 Matrix multiplication의 구현과 최적화 1. Introduction Problem Solving을 위해 C/C++ 을 쓰는 사람들에게 matrix multiplication의 구현은 귀찮은 일입니다. 당연히 많은 사람들이 이를 템플릿에 박아놓고 그대로 씁니다. 하지만, 문제의 제한에 따라 다양한 최적화의 여지가 있으며 일부는 탁월한 효과를 보입니다. 이 글에서는 가장 naive한 구현에서부터 특수한 맥락에서만 쓸 수 있는 코드까지 소개해보고자 합니다. 대부분의 코드는 제 경험으로부터 비롯하였으며, 따라서 C++의 reference type이나 STL(특히, , 등)을 쓰거나, class로 wrapping하는 코드는 다루지 않습니다. 2. 기본적인 구현 우선, matrix multiplication의 가장 일반적인 형태는 다음과 같습니다. $m.. 기본 이론 3 이번 글에서는 인접행렬의 거듭제곱에 대해 다루겠습니다. 인접행렬, adjacency matrix는 graph를 matrix로 나타낸 것입니다. 어떤 matrix $A$ 가 graph $G$ 의 adjacency matrix라는 것은 일반적으로 다음을 의미합니다. $G$의 임의의 두 vertices $i$ 에서 $j$ 로의 edge가 존재하면 $A_{ij}$ 의 값이 1, 그렇지 않으면 0 Adjacency matrix로 edge가 directed인 경우, weighted인 경우도 표현할 수 있습니다. directed가 아니면 $A_{ij}=A_{ji}=1$ 임이 자명합니다. 즉, $A_{ij} \ne A_{ji}$라면 directed graph일 것입니다. weighted의 표현은 간단하게 그 edge의.. 기본 이론2 기본 이론 1 이 글에서는 Exponentiation By Squaring을 이용하여 정사각행렬 A의 N 제곱을 구하는 방법을 알아보도록 하겠습니다. 1. Identity Matrix of Order N (한: N차 단위 행렬) Matrix라는 대상은 C/C++ 환경에서 보통 array 또는 vector로 구현됩니다. int array[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i == j) { array[i][j] = 1; } else { array[i][j] = 0; } } } (tutorial for getting an identity matrix) 위 코드에서 array를 바로 N차 단위 행렬이라고 할 수 있습니다.. 기본 이론 큰 자연수 A, B, M에 대해 $ A^{B}\left ( mod M \right ) $의 값을 필요로 하는 문제가 많습니다. 이 카테고리에서는 이런 문제를 몇 가지 풀어보려고 합니다. 이 글에서는 문제를 풀기 이전에 주요 개념을 간략하게 설명해보도록 하겠습니다. 1. Exponentiation By Squaring $x^{y}$를 분할 정복을 이용하여 빠르게 구하는 기법입니다. 이때 y의 이진수 꼴을 쓰는 경우 Binary Exponentiation이라고도 합니다. 실제 코드 전에 간단히 예시를 보겠습니다. (10^13) = (10^8) * (10^4) * (10^1) 13 = 1101 8 = 1000 4 = 0100 1 = 0001 구조가 보이나요? $x^{y}$에서 y를 binary로 나타낸 것을 .. 이전 1 다음