본문 바로가기

Algorithm/D. Math & Number Theory

 (25)
72. Discrete Square Root & Tonelli-Shanks Algorithm 이산 로그에 이어서 이산 제곱근(Discrete Square Root)에 대한 내용을 다룬다. 양의 정수 $m$에 대해 $a^2 \equiv x \pmod{m}$을 만족할 경우 $a$를 $x$의 이산 제곱근이라고 한다. 일반적으로 $a$와 $x$의 범위는 $0$ 이상 $m$ 미만으로 한정되며, 이 범위에서 정수 $x$의 이산 제곱근을 빠르게 구하는 방법이 존재한다. 일단 $\gcd(x, m) = 1$이라고 가정한다. 먼저 $m$이 소수인 경우 이산 제곱근을 구하는 방법을 알아본다. $m = 2$라면 $x$의 이산 제곱근이 $x$ 하나라는 것은 쉽게 알 수 있으므로 $m$이 홀수 소수인 경우만 고려하면 된다. 먼저 이산 제곱근이 존재하지 않는 경우를 처리해야 하는데, 페르마의 소정리에 의해 $a^{m-1}..
71. Order & Discrete Logarithm 모듈러 산술이 사용되는 이산 구조에서의 추가적인 연산에 대해 알아본다. 서로소인 두 정수 $a, m$와 양의 정수 $k$에 대해 $a^k \equiv 1 \pmod{m}$이고 $k$보다 작은 임의의 양의 정수 $k'$에 대해 $a^{k'} \not\equiv 1 \pmod{m}$일 때 $k$를 모듈러 $m$에 대한 $a$의 위수(Order)라고 하며 기호로는 $\text{ord}_m(a)$로 나타낸다. 오일러 토션트 함수의 성질에 의하면 $a^{\phi(m)} \equiv 1 \pmod{m}$이므로 $a$의 위수 $k$는 $\phi(m)$보다 커질 수 없으며 조금 더 확장하면 $k$는 $\phi(m)$의 약수가 되어야 한다. 모듈러 $m$에 대한 $a$의 위수가 $\phi(m)$일 때 $a$를 모듈러 $..
66. Inclusion-Exclusion Principle 포함-배제의 원리(Inclusion-Exclusion Principle)는 각 집합의 원소의 수를 이용하여 그것들의 합집합의 원소의 수를 구할 때 사용되는 원리이다. 포함-배제의 원리에 따르면 $n$개의 집합 $A_1, A_2, \ldots A_n$의 합집합의 원소의 개수는 다음과 같이 구할 수 있다. $$\left\vert \bigcup_{i=1}^n A_i \right\vert = \sum_{I \subset U} (-1)^{\left\vert I \right\vert +1} \left\vert \bigcap_{i \in I} A_i \right\vert$$ 이것을 해석하면, $n$개의 집합의 합집합의 원소의 개수는 $($집합 $1$개의 원소의 개수의 합$) - ($집합 $2$개의 교집합의 원소의 개..
63. Nim Game & Sprague-Grundy Theorem 님 게임(Nim Game)은 간단하면서도 게임 이론에서 중요한 역할을 하는 게임으로, 여기서 사용된 전략을 다른 많은 게임에 응용해서 적용할 수 있다. 님 게임은 $0$개 이상의 돌이 있는 $n$개의 더미에서 번갈아 가면서 돌을 가져가는 방식으로 차례를 진행한다. 가져가는 돌의 개수에는 제한이 없지만 한 차례에는 하나의 더미에서만 돌을 가져갈 수 있다. 더이상 돌을 가져갈 수 없는 플레이어가 게임에서 지게 된다. 님 게임에서 각각의 더미에 남아 있는 돌의 개수를 $[x_1, x_2, \ldots x_n]$이라고 하면 이 게임의 상태를 님 합(Nim Sum)으로 분류할 수 있다. 님 합 $s = x_1 \oplus x_2 \oplus \ldots \oplus x_n$이며, $\oplus$는 XOR 연산을 ..
62. Game Theory 게임 이론(Game Theory)은 상호 의존적이고 이성적인 의사 결정을 다루는 이론이다. 게임(Game)은 각각의 행위자들이 일정한 전략을 가지고 최고의 보상을 얻기 위해 벌이는 행위를 말하며, 알고리즘 문제에 적용할 경우 게임에서 승리하거나 최대한 좋은 결과를 얻기 위해 적절한 전략을 가지고 플레이하는 것을 의미한다고 할 수 있다. 게임 이론에서 모든 참가자는 최선의 선택을 하며 다른 참가자들 역시 최선의 선택을 할 것이라는 사실을 알고 있다고 간주한다. 또한 다음과 같은 사항이 존재한다. 모든 참가자는 정보를 가지고 있다. 게임의 초기 상태가 존재한다. 게임의 순서와 정해진 규칙이 존재한다. 참가자는 가능한 선택 중 어떤 것이든지 할 수 있다. 대부분의 게임은 다음과 같은 추가적인 제한을 갖는다. ..
61. Sum of Squares 이번 글에서는 임의의 자연수 $p$를 최소 개수의 제곱수의 합으로 나타내는 문제를 살펴본다. 먼저 $p$를 제곱수 $1$개의 합으로 나타낼 수 있으려면 $x^2=p$를 만족하는 정수 $x$가 존재해야 한다는 사실은 쉽게 알 수 있다. $p$가 처음부터 제곱수였다면 $p$를 제곱수 $1$개의 합으로 나타낼 수 있다. 다음으로 $p$를 제곱수 $2$개의 합으로 나타낼 수 있는 경우를 알아본다. 먼저 임의의 제곱수를 $4$로 나눈 나머지를 구하면 다음과 같다: $(2k)^2=4k^2$ $(2k+1)^2=4k^2+4k+1=4k(k+1)+1$ 그 밖의 경우가 존재하지 않으므로 제곱수를 $4$로 나눈 나머지는 $0$ 또는 $1$이고, 제곱수 $2$개를 더한 결과를 $4$로 나눈 나머지는 $0, 1, 2$가 될 수 ..
60. Strassen's Algorithm 스트라센 알고리즘(Strassen's Algorithm)은 행렬 곱셈을 $\Theta(n^3)$보다 빠른 시간에 하는 알고리즘이며 카라츠바 알고리즘과 유사하게 분할 정복을 이용하여 시간복잡도를 줄인다. 크기가 $n \times n$인 두 행렬 $A$와 $B$가 존재하고, $A$와 $B$의 곱이 행렬 $C$일 때 스트라센 알고리즘의 작동 방식은 다음과 같다. 먼저 각 행렬을 $4$등분해서 다음과 같이 나눈다. $$A = \begin{bmatrix} A_{1, 1} & A_{1, 2} \\ A_{2, 1} & A_{2, 2} \end{bmatrix}, B = \begin{bmatrix} B_{1, 1} & B_{1, 2} \\ B_{2, 1} & B_{2, 2} \end{bmatrix}, C = \begin..
59. Gaussian Elimination 가우스 소거법(Gaussian Elimination)은 연립일차방정식의 해를 구할 때 사용되는 행렬 연산이며, 그밖에도 다양한 방법으로 응용이 가능하다. 가우스 소거법은 행렬에 다음과 같은 세 가지 연산을 수행한다. 첫 번째 연산을 두 번째 연산과 세 번째 연산의 조합으로 대체할 수 있기 때문에 두 가지 연산이라고 해도 상관없지만 편의상 세 가지로 구분했다. $i$행과 $j$행을 서로 바꾼다. $i$행의 각 성분에 $0$이 아닌 실수 $k$를 곱한다. $i$행에 $j$행을 더한다. 가우스 소거법의 목표는 행렬의 랭크와 독립이 아닌 열 사이의 상관관계를 유지하면서 행렬을 행사다리꼴로 만드는 것이다. 이와 관련하여 다음 용어들을 알아 두는 것이 좋다. 피벗(Pivot, Leading Entry)은 각 행에서..

티스토리툴바