개요
유클리드 알고리즘(Euclidean algorithm), 또는 유클리드 호제법은 두 정수의 최대공약수(Greatest Common Divisor, GCD) 를 구하는 대표적인 알고리즘입니다.
이 알고리즘은 두 수의 나눗셈을 반복하여 나머지가 0이 될 때까지 계속 진행하고, 나머지가 0이 되는 순간의 나누는 수(제수)가 바로 두 수의 최대공약수가 된다는 원리를 이용합니다.
알고리즘의 원리는 다음과 같습니다.
두 정수 a, b (a > b)가 있을 때, a를 b로 나눈 나머지를 r이라 하면, 다음 관계가 성립합니다.
gcd(a, b) = gcd(b, r)
이 과정을 나머지 r이 0이 될 때까지 반복합니다.
결국, 마지막으로 나누는 수가 최대공약수가 됩니다.
예제
유클리드 호제법의 작동 원리를 간단한 파이썬 코드로 살펴봅시다.
유클리드 호제법을 이용한 최대공약수 구하기
def gcd(a, b):
while b != 0:
a, b = b, a % b # a를 b로 나눈 나머지를 새로운 b로 설정
return a
num1, num2 = 48, 18
print(f"{num1}와 {num2}의 최대공약수는 {gcd(num1, num2)}이다.")def gcd(a, b):
return gcd(b, a % b) if b > 0 else a단계 계산 과정 설명
- 48 ÷ 18 = 2, 나머지 12 gcd(48, 18) = gcd(18, 12)
- 18 ÷ 12 = 1, 나머지 6 gcd(18, 12) = gcd(12, 6)
- 12 ÷ 6 = 2, 나머지 0 gcd(12, 6) = gcd(6, 0)
따라서 6이 최대공약수가 됩니다.