두 개의 숫자 a와 b가 주어졌을 때, 재귀(Recursion) 방식으로 이 숫자들의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법을 알아보겠습니다. 최대공약수를 구하기 위해 널리 사용되는 유클리드 호제법(Euclidean Algorithm)을 활용합니다.
유클리드 호제법이란?
유클리드 호제법은 두 수의 최대공약수를 구하는 고전적인 알고리즘으로, 두 수 a와 b(a > b)에 대해 a를 b로 나눈 나머지를 이용해 문제를 반복적으로 축소해 나가는 방식입니다. 두 수가 같아지는 시점의 값이 바로 최대공약수가 됩니다.
예를 들어 입력이 a = 25, b = 45라면, 출력 결과는 5가 됩니다.
해결 접근 방식
다음 단계에 따라 문제를 해결할 수 있습니다.
- 두 인자 a, b를 받는 함수 gcd()를 정의합니다.
- a와 b가 같으면 a를 그대로 반환합니다. (재귀 종료 조건)
- a가 b보다 작으면 인자의 순서를 바꿔 gcd(b, a)를 호출합니다.
- 그 외의 경우(a > b)에는 gcd(b, a - b)를 호출하여 두 수의 차이로 문제를 축소합니다.
구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
def gcd(a, b):
if a == b:
return a
elif a < b:
return gcd(b, a)
else:
return gcd(b, a - b)
a = 25
b = 45
print(gcd(a, b))입력
25, 45
출력
5
동작 과정 살펴보기
위 코드가 실행되는 과정을 단계별로 살펴보면 다음과 같습니다.
- gcd(25, 45): 25 < 45이므로 gcd(45, 25) 호출
- gcd(45, 25): 45 > 25이므로 gcd(25, 20) 호출
- gcd(25, 20): 25 > 20이므로 gcd(20, 5) 호출
- gcd(20, 5): 20 > 5이므로 gcd(5, 15) 호출
- gcd(5, 15): 5 < 15이므로 gcd(15, 5) 호출
- gcd(15, 5): 15 > 5이므로 gcd(5, 10) 호출
- gcd(5, 10): 5 < 10이므로 gcd(10, 5) 호출
- gcd(10, 5): 10 > 5이므로 gcd(5, 5) 호출
- gcd(5, 5): 두 수가 같으므로 5 반환
최종적으로 최대공약수 5가 출력됩니다.
시간 복잡도 및 참고 사항
위 차감 기반 방식은 직관적이지만, 두 수의 차이가 클 경우 재귀 호출 횟수가 많아질 수 있습니다. 실무에서는 나머지 연산(%)을 사용하는 변형된 유클리드 호제법(gcd(b, a % b))이 더 효율적이며, 시간 복잡도는 O(log(min(a, b)))입니다. 또한 파이썬에서는 math 모듈의 math.gcd() 함수를 사용하면 별도 구현 없이 간편하게 최대공약수를 구할 수 있습니다.