[Python] 유클리드 알고리즘

유클리드 알고리즘은 두 수의 최대공약수를 구하는 방법으로, 기록이 남아 있는 가장 오래된 알고리즘이다

이는 gcd(a, b) == gcd(a-b, b) 임을 이용한다

 

( ∵

a, b의 공약수 g가 있다고 하자

a = a'g, b = b'g 이다

a-b = (a'-b')g 이므로

g는 a'-b', a-b, b의 공약수이다 )

 

코드는 다음과 같다

 

def gcd(a, b):
	if(a < b): a, b = b, a
	if(q == 0): return p
	return gcd(a-b, b)

 

하지만 더 최적화할 수 있다

a의 값이 충분히 클 때, 이 알고리즘은 적어도 a/b 번의 재귀 호출을 거칠 것이다

이를 a-b 대신, a%b로 취한다면, 보다 더 깔끔하게 동작할 것이다

 

코드는 다음과 같다

 

def gcd(x, y):
	if(y == 0): return x
	return gcd(y, x % y)
    
'''
x == 3, y == 5 일 경우
gcd(3, 5) -> gcd(5, 3) -> gcd(3, 2) -> gcd(2, 1) -> gcd(1, 0)
'''

 

이에 더불어서 확장된 유클리드 알고리즘도 있는데

이는 최대공약수가 아닌 부정방정식의 해를 구할 때 쓰이게 된다

예시로는 중국인 나머지 정리 문제가 있고, 암호학에서도 요긴하게 쓰인다고 한다