1. 유클리드 호제법(파이썬 코드)
a, b = 490, 350
while b:
a, b = b, a%b
print(a)
# 70풀어볼 문제: 최대공약수와 최소공배수(https://www.acmicpc.net/problem/2609)
2. 유클리드 호제법이란?
유클리드 호제법은 두 수가 서로(互 서로 호) 0이 될 때까지 덜어내면(除 덜 제) 최대공약수를 찾을 수 있는 알고리즘입니다.
기원전 3세기에 고대 그리스 수학자 유클리드가 집필한 <원론>에 명시되어 있습니다.
이는 명시적으로 기술된 가장 오래된 알고리즘으로도 알려져 있습니다.
3. 최대공약수를 구하는 과정 비교
490과 350의 최대공약수를 구하는 과정을 코드로 작성해봅시다.
단순하게 1씩 증가시켜가며 두 수를 동시에 나눌 수 있는 수(공약수)의 최대값을 찾습니다.
a, b = 490, 350
gcd = 0
cnt = 0
divisor = 1
while divisor <= min(a, b): # 나누는 수를 1씩 증가시키며 나누어지는 수보다 커지지 않을 때까지 반복합니다.
cnt += 1
if a % divisor == 0 and b % divisor == 0: # 두 수 모두 나누어 떨어지면(공약수) 값을 기록합니다.
gcd = divisor
divisor += 1
print(gcd)
# 70
print(cnt)
# 350코드로 구현하기 쉬운 방법이지만 연산 횟수가 350번으로 큰 수를 다루기에는 비효율적입니다.
다음으로 초등학교에서 배우는 방법입니다.
두 수를 동시에 나눌 수 있는 수(공약수)로 거듭 나누어 나눌 수 있는 수를 모두 곱하여 최대공약수를 구합니다.
a, b = 490, 350
gcd = 1
cnt = 0
while True:
for divisor in range(2, min(a, b)): # 나누는 수를 찾기 위해 하나씩 넣어봅니다.
cnt += 1
if a % divisor == 0 and b % divisor == 0: # 두 수 모두 나누어지는 경우를 찾습니다.
a //= divisor # 두 수를 나누는 수로 나눕니다.
b //= divisor
gcd *= divisor # 나누는 수를 계속해서 곱합니다.
break
else:
break # 나눌 수 있는 수가 없으면 종료합니다.
print(gcd)
# 70
print(cnt)
# 14파이썬으로 위와 같이 코드를 작성할 수 있으며, 총 14번의 연산 횟수를 거칩니다.
물론 주어진 수보다 작은 모든 소수(prime number)를 구한 후 소수로 나누어도(소인수분해) 되지만, 소수를 구하는 과정이 추가적으로 필요합니다.
마지막으로 호제법입니다.
한 쪽이 0이 될 때까지 빼면, 다른 한 쪽은 70이 됩니다.
따라서 최대공약수는 70입니다.
a, b = 490, 350
cnt = 0
while b != 0:
cnt += 1
a, b = b, a%b
gcd = a
print(gcd)
# 70
print(cnt)
# 3호제법으로 연산할 경우 이전과 비교해서 코드로 구현하기 편하고 간결하다는 것을 알 수 있습니다.
게다가 연산 횟수도 3회로 가장 효율적인 것을 알 수 있습니다.
이렇듯 유클리드 호제법은 간결한 코드와 동작이 효율적이라는 장점을 가진 좋은 알고리즘이라고 할 수 있습니다.
