본문 바로가기

Algorithm/D. Math & Number Theory

 (25)
58. Rank of Matrix 행렬의 랭크를 쉽게 이해하기 위해서는 벡터의 독립에 대해서 알 필요가 있다. 두 벡터 $\vec{u}, \vec{v}$가 다음과 같은 조건을 만족할 경우 서로 독립(Independence)이라고 한다. $$a\vec{u}+b\vec{v}=\vec{0} \to a=b=0$$ 이것을 다르게 해석하면 두 개의 벡터가 독립일 때 그 벡터들을 이용해서 공간 내의 모든 좌표를 나타낼 수 있는 $2$차원 공간이 존재한다는 의미가 된다. 이와 비슷하게 $n$개의 벡터 $\vec{v_1}, \vec{v_2}, \ldots \vec{v_n}$가 다음과 같은 조건을 만족할 경우 서로 독립이라고 한다. $$a_1\vec{v_1}+a_2\vec{v_2}+\ldots+a_n\vec{v_n}=\vec{0} \to a_1=a_2=\..
57. Matrices 이번 글에서는 선형대수학(Linear Algebra)에 대한 내용을 다룬다. 선형대수학은 덧셈과 곱셈을 통한 변화에 초점을 두는 수학의 한 분야이며, 적절한 표현을 이용하여 선형방정식의 해를 구하는 것을 핵심으로 하고 있다. 선형대수학에서 중요하게 다뤄지는 개념으로 행렬(Matrices)과 벡터(Vectors)가 존재하는데, 벡터에 관한 자세한 내용은 카테고리 G에서 다루고 여기서는 행렬에 관한 내용 위주로 다루기로 한다. 행렬은 수나 식을 직사각형 모양으로 배열한 것으로 행(Row, 가로줄)의 수가 $n$, 열(Column, 세로줄)의 수가 $m$인 경우 $n \times m$ 행렬이라고 한다. 또한 각각의 수나 식을 행렬의 성분(Entry)이라고 하고, 각각의 행을 행벡터(Row Vector), 각각..
56. Karatsuba's Algorithm 두 정수의 곱을 구할 때, 곱한 결과가 일반적인 정수 자료형에 저장하기에는 너무 큰 경우 정수를 문자열 형태로 저장한 후 직접 곱셈을 구현해야 한다. $100\text{~}1000$자리 정도의 정수를 곱할 때는 일반적인 $\Theta(n^2)$ 곱셈을 구현해도 괜찮지만 자릿수가 $10000$ 단위가 되면 $\Theta(n^2)$ 곱셈은 속도가 많이 느려지게 된다. 이때 카라츠바 알고리즘(Karatsuba's Algorithm)을 이용하면 곱셈의 시간복잡도를 $\Theta(n^{\text{lg }3})$으로 줄일 수 있다. 카라츠바 알고리즘은 분할 정복을 이용하여 정수의 곱을 계산하는 과정에서 중복된 계산을 유도한다. 계산이 중복되면 한 번만 해도 되므로 그만큼 연산 횟수가 줄어들게 된다. 곱해야 하는 두..
55. Permutation Cycle Decomposition 순열(Permutation)은 $1$ 이상 $n$ 이하의 정수가 한 번씩 등장하는 특수한 형태의 수열이다. $n$은 순열의 길이이며 $0$보다 큰 정수이다. 이 글에 나오는 순열과는 비슷하지만 약간 다르다. 특정한 조건을 만족하는 순열의 개수를 다음과 같은 공식으로 구할 수 있다. 길이가 $n$인 순열의 개수는 $n!$이다. 길이가 $n$인 순열 $a: \{a_1, a_2, \ldots a_n\}$ 중 $a_i=i$를 만족하는 $i$가 존재하지 않는 순열의 개수를 $f(n)$이라고 하면, $f(1)=0, f(2)=1$이고, $n \ge 3$인 경우 $f(n)=(n-1)(f(n-2)+f(n-1))$이다. 또한 그런 $i$가 $k$개 존재하는 순열의 개수는 $_n\mathrm{C}_k \times f(n-k..
54. Euler's Totient Function 오일러 토션트 함수(Euler's Totient Function)는 모듈러 곱셈 역원이 존재하는 수의 개수를 구하는 함수이며, 기호로는 $\phi$를 사용한다. 즉, 임의의 양의 정수 $n$에 대해 $\phi(n)$은 $n$ 이하의 양의 정수 중 $n$과 서로소인 것의 개수와 같다. 오일러 피(파이) 함수(Euler's Phi Function)라고도 한다. 오일러 토션트 함수의 결과값은 다음과 같은 두 가지 공식을 이용하여 구할 수 있다. $p$가 소수이고 $n = p^k$일 때, $\phi(n)=p^{k-1}(p-1)$이다. $n$과 $m$이 서로소일 때, $\phi(nm) = \phi(n) \phi(m)$이다. $n$의 소인수를 중복 없이 나열한 결과가 $p_1, p_2, \ldots, p_k$일 때..
53. Lucas' Theorem 뤼카 정리(루카스 정리, Lucas' Theorem)는 이항계수 $_n\mathrm{C}_r$을 소수 $p$로 나눈 나머지를 구할 때 사용되는 정리이다. 이 정리를 이용하면 $n$과 $r$이 클 때에도 이항계수를 빠르게 구할 수 있다. 정리의 내용은 다음과 같다. $$_n\mathrm{C}_r=(_{\lfloor n/p \rfloor}\mathrm{C}_{\lfloor r/p \rfloor})(_{n\,\bmod\,p}\mathrm{C}_{r\,\bmod\,p})\bmod p$$ 만약 $n
52. Chinese Remainder Theorem 정수론에서 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)는 서로소인 $n$개의 양의 정수 $m_1, m_2, \ldots, m_n$과 $0 \le a_i < m_i$ $(1 \le i \le n)$를 만족하는 $n$개의 정수 $a_1, a_2, \ldots a_n$에 대해 다음 $n$개의 합동식 $$x \equiv a_i \pmod{m_i} \quad (1 \le i \le n)$$ 을 모두 만족하는 $0$ 이상 $\prod_{i = 1}^n m_i$ 미만의 정수 $x$가 유일하게 존재한다는 정리이다. 이 정리의 역사는 $5$세기로 거슬러 올라간다. 중국 남북조 시대의 수학서인 『손자산경』에는 다음과 같은 문제가 등장하는데, 이것이 중국인의 나머지 정리가 처음으로 등장하는..
51. Extended Euclidean Algorithm 확장 유클리드 호제법(확장 유클리드 알고리즘, Extended Euclidean Algorithm)은 다음과 같은 식에서 정수 $a, b$가 주어졌을 때 식을 만족하는 정수 $x, y$를 구하는 알고리즘이다. $$ax+by=\gcd(a,b)$$ 확장 유클리드 호제법은 유클리드 호제법을 이용하여 $x$와 $y$를 구한다. 만약 $a$와 $b$를 각각 $b$, $a\,\bmod\,b$로 바꿨을 때 다음 식을 만족하게 하는 $x', y'$을 알고 있다면, $$bx'+(a\,\bmod\,b)y'=\gcd(a,b)$$ $a\,\bmod\,b=a-b\lfloor a/b \rfloor$이므로 식을 다음과 같이 변환할 수 있다. $$bx'+(a-b\lfloor a/b \rfloor)y'=\gcd(a,b)$$ $$ay'..

티스토리툴바