[알고리즘] 유클리드 호제법

서론

최대공약수를 이용하는 코테 문제를 풀던 도중 계속해서 시간 초과가 나길래 뭐때문에 문제가 나는가 싶었다.

https://school.programmers.co.kr/learn/courses/30/lessons/135807

일반적인 최대공약수를 구하는 방식으로 했더니 시간 초과는 계속 나고 문제는 풀어야지 직성에 풀리고 그래서 다른 방식이 있나 찾아보았더니 해당 알고리즘을 찾았다.

유클리드 호제법이란?

개요

$a$ 와 $b$ 라는 숫자가 존재하고 이에 해당하는 최대공약수가 $d$ 와 $a$ 를 $b$ 로 나눴을 때의 나머지 $r$ 이라는 숫자가 있을 경우 다음과 같은 식이 성립이 된다.

$(a,b) = (b,r) = d$

전제조건

• $a \ge b$
• $a$ 와 $b$ 의 최대공약수는 $d$ 이다.
• $a$ 를 $b$ 로 나눈 나머지는 $r$ 이다.

증명

$a \ge b$ 이기에 다음과 같은 식이 성립이 된다.

$a = bq + r$

그리고 $d$ 가 $a$, $b$ 의 최대공약수이기에 다음과 같이 정의를 할 수 있고 이를 대입하면 그 다음 식이 된다.

$a = d\alpha, b=d\beta$

$d\alpha = d\beta q + r$

이렇게 될 경우 $\alpha$ 와 $\beta$ 는 서로소이다.
위 식을 $r$ 을 위한 식으로 이항하고 정리하면 다음과 같다.

$r = d(\alpha - \beta q)$

정리를 하면

$d\alpha = d\beta q + d(\alpha-\beta q)$

$b$ 와 $r$ 의 최대공약수가 $d$ 가 되기 위해서는
$\beta$ 와 $\alpha - \beta q$ 가 서로소여야 한다.

만약 서로소가 아닌 경우에는 어떻게 될까?

$\beta$ 와 $\alpha - \beta q$ 사이에 공약수 $c$ 가 있다고 하자.

$\beta = cx, \alpha-\beta q = cy$

$d\alpha = dcxq + dcy$
$d\alpha = cd(xq + y)$
$\alpha = c(xq+y)$

즉, $\alpha$ 와 $\beta$ 는 각각

$\alpha = c(xq+y)$
$\beta = cx$

가 되고 c 라는 약수를 공통적으로 가지게 된다.

이는, 위에서 나왔던 '$\alpha$ 와 $\beta$ 는 서로소이다.' 를 위반하므로 '$\beta$ 와 $\alpha - \beta q$ 가 서로소가 아니다.' 라는 명제는 거짓이 된다.

그러므로, $\beta$ 와 $\alpha - \beta q$ 는 서로소이고 이에 따라 $b$ 와 $r$ 의 최대공약수는 $d$ 가 된다.

코딩 (python)

유클리드 호제법을 이용해서 최대공약수를 구하는 것은 반복문을 이용하면 된다.

$(a,b) = (b,r)$ 이기에 반복하여서 $a$ 자리에는 $b$ 를, $b$ 자리에는 $r$ 을 넣어준다.

만약 $r$ 이 0이 된다면 해당 $b$ 가 최대공약수가 된다.

def euclidean_algorithm(a,b):
	while b > 0:
    	a, b = b, a%b
    return a