1. 유클리드 호제법/알고리즘 (Euclidean Algorithm)
ㅇ 두 정수의 최대공약수를 빠르게 계산해내는 알고리즘
ㅇ 최대공약수를 구하는 통상적인 방법으로는,
- 두 수를 소인수분해한 후, 그 중 공통되는 소수 중 제일 큰 것을 찾아가는 복잡한 방법을 씀
- 그러나, 소인수분해(어떤 수를 소수의 곱셈 형태로 인수분해하는 것) 자체도 쉽지 않음
- 또한, 두 약수 리스트 중 공통으로 들어있는 제일 큰 수를 찾는 것도 만만치 않음
2. 유클리드 호제법/알고리즘의 표현
ㅇ 두 수의 나눗셈을 반복하여 나머지가 0 될 때, 최대공약수가 구해지는 방법
- 例) gcd(21,9) → a = 21, b = 9
. a = b x q + r ☞ 나눗셈 관계식 참조
. 21 = 9 x 2 + 3 → b = 9, r = 3
.. 여기서, 나온 나머지 3으로, 방금 나누어지는데 사용된 수 9를 나눔
. 9 = 3 x 3 + 0 → b = 3, r = 0 (나누어떨어짐)
.. 여기서, 나머지가 0이 되므로, 이때 나누는 수 3이 최대공약수가 됨
. 따라서, gcd(21,9) = 3
ㅇ 알고리즘 표현 형태
ㅇ 입력 : r[0], r[1]
ㅇ 출력 : gcd ( r[0], r[1] )
Euclidean ( r[0], r[1] ) {
초기화 : i = 1 ;
while ( r[i] ≠ 0 ) {
r[i] = r[i-2] mod r[i-1] ;
}
return gcd ( r[0], r[1] ) = r[i-1]
}
ㅇ 알고리즘 요약
- gcd(a, b) = gcd(b, a mod b) 라는 성질을 반복적으로 적용
- 연산은 나눗셈 (mod) 만 사용
- 계산 복잡도는 매우 효율적 : 입력 크기에 대해 O(log n)
※ 결국, 유클리드 알고리즘은,
- 단순히 나눗셈 만 되풀이하는 것 만으로도 최대공약수가 구해지게 됨
. 즉, 나눗셈을 되풀이하다가 마지막에 나누어떨어질 때,
. 그 때 나누는 수가 최대공약수가 됨
※ 한편, 마지막이 1이 되는 경우(즉, 두 수의 최대공약수가 1 인 경우)에,
- 이 때의 두 수는 서로소(Relatively Prime) 라고 함
3. 파이썬 구현
ㅇ 반복문 기반 구현
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
print(gcd(21, 9)) # 출력: 3
print(gcd(14, 25)) # 출력: 1 (서로소)
ㅇ 배열 r[i] 형태를 반영한 구현
def euclidean(r0, r1):
r = [r0, r1]
i = 1
while r[i] != 0:
r.append(r[i-1] % r[i])
i += 1
return r[i-1]
print(euclidean(21, 9)) # 3
print(euclidean(14, 25)) # 1
ㅇ 재귀적 구현
def gcd_recursive(a, b):
if b == 0:
return a
return gcd_recursive(b, a % b)