Euclidean Algorithm (p. 506)
호제법?#
이 알고리즘은 유클리드 호제법이라고도 부른다. 호제법(互除法)의 뜻은 서로 나눈다는 뜻이다. 영어로는 그냥 ‘서로 나눈다’는 뜻 없이 Algorithm이라 표기한다. 우리나라 표현도 유클리드 호제법이란 표현은 좀 올드하고 요즘은 그냥 유클리드 알고리즘이라 부른다.
유클리드 알고리즘이란?#
$$ a = bq+r $$위와 같이 a가 b로 나누었을 때 몫이 q이고 나머지가 r이라 하자.
그러면 아래의 식이 성립한다.
$$ gcd(a,b) = gcd(b,r) $$참 놀라운 발견이 아닌가 싶다. 심지어 이 식이 쓰인게 기원전 300년경 이라고 한다.
유클리드 알고리즘 증명#
증명 방법은 아래와 같다.
1. a, b의 공약수가 b, r의 공약수임을 보인다.#
$$ d\;|\;a $$위의 식은 d divides a란 뜻으로, d가 a를 나눈다, 즉, a가 d로 나누어 떨어진다는 뜻이다.
명확한 수학의 정의로는 $d = ak$를 만족하는 정수 $k$가 존재한다는 뜻이다.
이제 그러면 정수 d가 아래의 식과 같다고 하자. ( $\land$는 Logical AND로 C++의 &&를 의미한다.)
그러면 아래 식을 만족하는 경우를 보이면 된다.
$$ d\;|\;b \quad\land\quad d\;|\;r $$$d\;|\;b$ 는 이미 처음 제시한 식에 있으므로 증명해 보일 것이 없고, $d\;|\;r$ 만 증명하면 된다.
$$ a = bq+r $$$$ \Rightarrow\quad r = a-bq $$$$ \Rightarrow \quad d\;|\;r = d\;|\;(a-bq) $$여기서 a는 d로 나누어 떨어지고 ( $d\;|\;a)$
-bq도 d로 나누어 떨어지므로 ( $d\;|\;b \Rightarrow d\;|\;b \cdot (\text{-}q) \Rightarrow d\;|\;\text{-}bq$ )
$$ \therefore d\;|\;(a-bq) \Rightarrow d\;|\;r $$2. b, r의 공약수가 a, b의 공약수임을 보인다.#
1번과 같은 방식으로 보이면 된다. 이미 한참 설명했으므로 깔끔하게 식만 써본다.
1) 가정#
$$ a = bq+r $$$$ d\;|\;b \quad\land\quad d\;|\;r $$2) 증명#
$$ d\;|\;b \Rightarrow d\;|\;bq $$$$ d\;|\;r $$$$ d\;|\;bq \quad\land\quad d\;|\;r\quad\Rightarrow\quad d\;|\;(bq+r) $$$$ bq+r=a \quad\Rightarrow\quad d\;|\;a $$3. 위의 1,2번이 성립하면 a,b의 최대공약수와 b,r의 최대공약수가 같다는 뜻이 된다.#
1번의 증명은 a, b 공약수의 집합이 b, r 공약수의 집합의 부분집합임을 보인 것이고, 2번의 증명은 그 역인 b, r 공약수 집합이 a, b 공약수 집합의 부분집합임을 보인 것이므로, a, b 공약수 집합은 b, r 공약수 집합과 같다.
여기서 최대 공약수(GCD: Greatest Common Divisor)란, 공약수 집합의 모든 원소를 곱하여 만드는 것이므로 두 공약수 집합이 같다는 것은 최대 공약수가 같다는 것과 같다.
유클리드 알고리즘을 사용한 GCD 구하기 (코드 구현)#
#include <bits/stdc++.h>
using namespace std;
int gcd(int b, int s) {
if(s==0) return b;
else return gcd(s,b%s);
}
int main() {
int b=1428, s=732;
//1428, 732라는 두 수의 최대공약수(GCD)를 구한다.
printf("gcd(%d,%d) = %d\n",b,s,gcd(b,s));
return 0;
}유클리드 알고리즘으로 GCD 구하기 시간복잡도#
$$ O(logN)\quad(N=min(a,b)) $$$gcd(a,b)$는 $a = bq+r$에서 $r=0$이 될 때까지 $a,b$로 들어오는 값을 줄여나가므로 $r=0$이 되는데 걸리는 재귀함수의 깊이가 어느 정도 되는지 파악하는 것이 관건이다.
최대 공약수 $gcd(a,b)$를 구하기 까지의 여러 단계를 우선 써보자.
$$ r_0 = r_1q_0 + r_2 \quad (r_o\text{=}a,\; r_1\text{=}b) $$$$ r_1 = r_2q_2 + r_3 $$$$ r_2 = r_3q_3 + r_4 $$$$ ... $$$$ r_n = r_{n+1}q_{n+1}+r_{n+2} $$위의 최대 공약수 구하는 시간이 최악이 되려면, $r_{n+2}\text{=}0$이 되는 n값의 크기가 커져야 한다는 뜻이다. 즉, 이런 최악의 경우는 모든 단계에서 $q_i\text{=}1$이 되는 경우임을 알 수 있다. 왜냐하면, 마지막 단계의 식을 나머지인 $r_{n+2}$에 대해서 쓰면
$$ r_{n+2} = r_n-r_{n+1}q_{n+1} $$인데, $r_{n+2}$값이 최대한 커져야 위에서 식을 적어주는 단계가 최대한 늘어날 것이므로 그러한 자연수 $q$값은 1이기 때문이다.
그러면 $q$값이 1이 되도록 위의 모든 단계의 식을 바꿔보면, $r_n$은 피보나치 수열을 뜻하는 것을 알 수 있다.
피보나치 수열 일반식 구하기#
피보나치 수열의 점화식은 아래와 같다.
$$ F_n = F_{n-1} + F_{n-2} \quad (n\ge2\; \land \;F_0\text{=}0 \;\land\; F_1\text{=}1) $$이는 2차 선형 동차 점화식(second-order linear homogeneous recurrence relation)이므로 $r^n$꼴의 해를 가정하여 특성방정식(characteristic equation)을 구할 수 있다. 따라서 아래와 같이 가정하면,
피보나치 수열 점화식은 아래와 같이 쓸 수 있다.
$$ r^n = r^{n-1} + r^{n-2} $$양변을 $r^{n-2}$로 나누고
$$ \Rightarrow r^2 = r+1 $$이 식을 풀면 아래와 같이 두 근을 구할 수 있다.
$$ \therefore r = \frac{(1 \pm \sqrt{5})}{2} $$그러면 맨 처음 언급했듯이 이 피보나치 수열 점화식이 2차 선형 동차 점화식이므로, 그 일반해는 다음과 같은 형태로 나타낼 수 있다.
이제 초기값 $F_0\text{=}0,\; F_1\text{=}1$을 만족하는 $A,B$를 찾으면 아래와 같다.
$$ F_0 = A + B = 0 $$$$ \Rightarrow B = \text{-}A $$$$ F_1 = A\left(\frac{1+\sqrt{5}}{2}\right) + B\left(\frac{1-\sqrt{5}}{2}\right)=1 $$$$ \Rightarrow A\left(\frac{1+\sqrt{5}}{2}\right) - A\left(\frac{1-\sqrt{5}}{2}\right)=1 $$$$ \therefore A \text{=} \frac{1}{\sqrt{5}},\;B\text{=}-\frac{1}{\sqrt{5}} $$그러므로 피보나치 수열의 일반항은 아래와 같다.
$$ F_n = \frac{1}{\sqrt{5}}\left(\left( \frac{1+\sqrt{5}}{2} \right)^n-\left( \frac{1-\sqrt{5}}{2} \right)^n\right) $$여기서 n이 커질수록 $\left(\frac{1-\sqrt{5}}{2} \right)^n \rightarrow0$이므로, $F_n$은 다음과 같이 표현할 수 있다.
$$ F_n \approx \frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2} \right)^n $$이제 위 식은 사실 어떤 값의 지수승이라는 것이 중요하다. 그래서 그러한 핵심만
보기 위해 n승 안의 값을 기호로 표기해본다. (원래 수학에서 n승안에 있는 값을
황금비(Golden Ratio)라 하고, 보통 파이( $\varphi$ ) 로 표기한다.)
이 식의 의미를 살펴보면 아래와 같다.
$gcd(a,b)$를 구하는 최악의 경우는 피보나치 수열의 형태이고, 여기서 나머지가 0이 되기까지 식의 개수($n$)가 시간복잡도가 되므로, $\frac{\varphi^n}{\sqrt{5}}$이라는 값은 $O(n)$의 시간이 걸림을 알 수 있다. 그러면 $\frac{\varphi^n}{\sqrt{5}}=N$으로 나타내면, $O(n) = O(logN)$이다.
$$ \therefore 최대공배수를\;구하는\;시간복잡도는\;O(logN)이다. $$