이 글에서는 두 수의 최대공약수(GCD)를 구하는 문제를 파이썬으로 해결하는 방법을 알아보겠습니다.
문제 정의
주어진 두 개의 숫자에 대해 최대공약수(GCD)를 계산하고 그 결과를 출력하는 것이 목표입니다.
두 수의 최대공약수(Greatest Common Divisor, GCD)란 두 수를 모두 나눌 수 있는 가장 큰 수를 의미합니다. 예를 들어, 12와 18의 최대공약수는 6입니다.
유클리드 호제법이란?
유클리드 호제법(Euclidean Algorithm)은 고대 그리스 수학자 유클리드가 제시한 방법으로, 두 수의 최대공약수를 효율적으로 구하는 알고리즘입니다.
핵심 원리는 다음과 같습니다.
- 두 수 a와 b(a > b)에 대해 a를 b로 나눈 나머지 r을 구합니다.
- a와 b의 GCD는 b와 r의 GCD와 같습니다.
- 나머지가 0이 될 때까지 이 과정을 반복하며, 나머지가 0일 때의 나누는 수가 곧 최대공약수입니다.
이 방식은 반복적으로 나눗셈을 수행하다가 나머지가 0이 되면 종료하는 재귀적 구조로 자연스럽게 구현할 수 있습니다.
구현 코드
# 유클리드 호제법을 이용한 최대공약수 계산
def gcd(a, b):
if a == 0:
return b
return gcd(b % a, a)
a = 11
b = 15
print("gcd of", a, "&", b, "is =", gcd(a, b))실행 결과
gcd of 11 & 15 is = 1
코드 설명
위 코드에서 함수 gcd(a, b)는 재귀적으로 동작합니다.
- 기저 조건(Base Case): a가 0이면 b가 곧 최대공약수이므로 b를 반환합니다.
- 재귀 호출: 그렇지 않으면
gcd(b % a, a)를 호출하여 나머지 연산을 반복합니다.
예를 들어 a=11, b=15인 경우 다음과 같이 진행됩니다.
- gcd(11, 15) → gcd(15 % 11, 11) = gcd(4, 11)
- gcd(4, 11) → gcd(11 % 4, 4) = gcd(3, 4)
- gcd(3, 4) → gcd(4 % 3, 3) = gcd(1, 3)
- gcd(1, 3) → gcd(3 % 1, 1) = gcd(0, 1)
- a가 0이 되므로 결과는 1
모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 재귀 호출 단계에서 변수 값의 변화를 추적해 보면 알고리즘의 흐름을 쉽게 이해할 수 있습니다.
마무리
이번 글에서는 파이썬을 활용해 기본 유클리드 호제법으로 두 수의 최대공약수를 구하는 방법을 살펴보았습니다. 유클리드 호제법은 시간 복잡도가 O(log(min(a, b)))로 매우 효율적이기 때문에 암호학, 분수 약분 등 다양한 분야에서 널리 활용됩니다. 재귀뿐만 아니라 while문을 사용한 반복문 버전으로도 구현할 수 있으니 여러 방식으로 직접 작성해 보시길 권장합니다.