44. Euclidean Algorithm

유클리드 호제법(유클리드 알고리즘, Euclidean Algorithm)은 두 다항식의 최대공약다항식을 빠르게 구하는 알고리즘이다. 일반적으로 차수가 $1$ 이상인 두 다항식의 최대공약다항식을 구하는 상황은 자주 발생하지 않으며 대부분 차수가 $0$인 두 다항식, 즉 두 정수의 최대공약수를 구하기 위해 유클리드 호제법을 이용하게 된다.

 

유클리드 호제법의 내용은 다음과 같다. ${\color{#0000FF}{\gcd(a, b)}}$는 $a$와 $b$의 최대공약다항식을 의미한다.

$a$, $b$가 다항식이고 $a$를 $b$로 나눈 나머지를 $c$라고 하면 $\gcd(a,b)=\gcd(c,b)$이다. $(b \ne 0)$

 

유클리드 호제법의 증명은 다음과 같다. 

• $a$, $b$가 $a \ge b \ge 0$, $a > 0$을 만족하는 정수라고 하면, $b=0$일 경우 $\gcd(a,b)=a$이다. $b>0$일 경우 $a$를 $b$로 나눈 나머지를 $c$라고 하면 $0 \le c < b$이고 $a=bx+c$로 나타낼 수 있다. 또한 $\gcd(a,b)=k$라고 하면 $a=pk$, $b=qk$로 나타낼 수 있다. 이때 $p$와 $q$는 서로소(Coprime)이다. 두 수가 서로소라는 것은 두 수의 최대공약수가 $1$인 것과 동치이다. ($k$, $p$, $q$, $x$는 정수)
• 식 $a=bx+c$에서 $a$와 $b$를 각각 $pk$, $qk$로 치환하면 $pk=qxk+c$, $(p-qx)k=c$이므로 $c$는 $k$의 배수이다. $p-qx=r$이라고 하면 $c=rk$이다. $\gcd(c,b)=\gcd(rk,qk)=k \times \gcd(r,q)$이므로 $\gcd(r,q)=1$임을 보여야 한다.
• $\gcd(r,q)=k'$라고 하면, $r=r'k'$, $q=q'k'$이라고 할 수 있다. 이때 $pk=qxk+rk=q'k'xk+r'k'k=kk'(q'x+r')$이므로 $p=k'(q'x+r')$이다. $p$와 $q$가 모두 $k'$의 배수이므로 $p$와 $q$가 서로소가 되려면 $k'=1$이어야 한다. 따라서 $\gcd(r,q)=1$이고, $\gcd(a,b)=\gcd(c,b)$이다.

$a$와 $b$가 $1$차 이상의 다항식인 경우에도 거의 같은 방법으로 증명이 가능하다.

 

유클리드 호제법으로 최대공약수를 구하는 함수의 구현은 다음과 같다.

int gcd(int x, int y)
{
    if(y == 0)return x;
    else return gcd(y, x % y);
}

C++의 경우 헤더파일 <bits/stl_algo.h>에 __gcd 함수가 정의되어 있으므로 이 함수를 사용하는 것도 좋다. <bits/stl_algo.h> 헤더파일 대신 <algorithm> 헤더파일을 인클루드해도 된다.

 

[연습문제]

 

BOJ 2609. 최대공약수와 최소공배수 (Silver V)

최대공약수는 유클리드 호제법을 이용하면 구할 수 있다. 다만 이 문제의 경우 입려값의 범위가 작아서 $1$부터 $10000$까지를 일일히 확인해도 된다. 두 수 $a$, $b$의 최소공배수는 $a \times b \div \gcd(a,b)$와 같다. 이 문제에는 해당사항이 없지만 어떤 문제들의 경우 최소공배수를 구하는 과정에서 $a \times b$가 오버플로우를 발생시킬 가능성이 존재하기 때문에 $a \div \gcd(a,b) \times b$와 같이 나눗셈을 먼저 하고 곱셈을 나중에 하는 식으로 구현하는 것이 안전하다.

 

BOJ 1735. 분수 합 (Silver III)

두 분수를 통분해서 더한 뒤 약분한다. 약분 과정에서 유클리드 호제법으로 분모와 분자의 최대공약수를 찾는다.

 

→ solved.ac tag: euclidean