본문 바로가기

Algorithm

 (143)
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위의 식을 다르게 해석하면, $n$과 $r$을 $p$진법으로 나타냈을 때 $i$번째 자리의 자리값을 각각 $n_i, r_i$라고 하면 $_n\mathrm{C}_r$을 $p$로 나눈 나머지는 모든 $_{n_i}\mathrm{..
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, EGCD)은 다음과 같은 식에서 정수 $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'..
50. Pigeonhole Principle 비둘기집의 원리(Pigeonhole Principle)는 $(n+1)$개의 물건을 $n$개의 상자에 빠짐없이 넣은 경우 최소한 한 개의 상자에는 두 개 이상의 물건이 들어간다는 원리로, 보통 비둘기와 비둘기집에 빗대어 표현하기 때문에 이런 이름을 가지게 되었다. 이를 일반화하면 $n$개의 물건을 $m$개의 상자에 빠짐없이 넣었을 때 $\lceil n/m \rceil$개 이상의 물건이 들어간 상자가 하나 이상 존재한다는 의미가 된다. 이 원리를 이용해서 풀 수 있는 문제들의 경우 제대로 접근하지 못하면 괜히 어려운 풀이를 생각하다가 헤매기 쉬우므로 주의해야 한다. [연습문제] BOJ 21099. Four XOR (Platinum V)더보기$n$개의 수의 범위가 $10$만 이하이므로 여기서 임의로 $2$개의..
49. Sieve of Eratosthenes 에라토스테네스의 체(Sieve of Eratosthenes)는 구간 내의 소수를 빠르게 찾아야 할 때 사용되는 방법이다. 이것을 이용하면 여러 개의 수를 동시에 소인수분해하는 것도 가능하고, 더 응용하면 약수의 개수나 약수의 합 등을 빠르게 구하는 것도 가능하다. 에라토스테네스의 체를 이용하여 소수를 찾는 과정은 다음과 같다. 일단 소수를 구하려는 범위 내의 수를 차례로 나열한다. 여기서는 $n=120$이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 4..

티스토리툴바