최대공약수(GCD, Greatest Common Divisor)란 두 숫자를 모두 나눌 수 있는 가장 큰 수를 의미합니다.
예를 들어 63과 21이라는 두 숫자가 있다고 가정해 보겠습니다.
63 = 7 * 3 * 3 21 = 7 * 3
두 수의 공통 약수 중 가장 큰 값은 7 × 3 = 21이므로, 63과 21의 최대공약수는 21입니다.
재귀적 유클리드 호제법이란?
유클리드 호제법(Euclidean Algorithm)은 두 양의 정수 a와 b에 대해 b와 a % b(a를 b로 나눈 나머지)를 반복적으로 계산하다가, b가 0이 되는 시점의 a값이 곧 최대공약수가 된다는 원리를 이용합니다. 이 과정을 함수가 자기 자신을 호출하는 재귀(recursion) 방식으로 구현할 수 있습니다.
C++ 구현 예제
다음은 재귀적 유클리드 호제법을 사용하여 두 숫자의 최대공약수를 구하는 C++ 프로그램입니다.
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Enter the values of a and b: 105 30 GCD of 105 and 30 is 15
코드 동작 원리
위 프로그램에서 핵심 역할을 하는 것은 재귀 함수 gcd()입니다. 이 함수는 a와 b 두 개의 매개변수를 받으며, 동작 방식은 다음과 같습니다.
- 종료 조건: b가 0이면 더 이상 나눌 수 없으므로 a를 그대로 반환합니다.
- 재귀 호출: b가 0이 아니면, gcd() 함수는 인자로 (b, a % b)를 전달하며 자기 자신을 다시 호출합니다.
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}main() 함수에서는 사용자로부터 두 정수 a와 b를 입력받은 뒤, gcd() 함수를 호출하여 그 결과값(두 수의 최대공약수)을 화면에 출력합니다.
int main() {
int a , b;
cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}단계별 호출 과정 살펴보기
입력값이 105와 30일 때, gcd() 함수는 다음과 같은 순서로 재귀 호출됩니다.
- gcd(105, 30) → 30은 0이 아니므로 gcd(30, 105 % 30) = gcd(30, 15) 호출
- gcd(30, 15) → 15는 0이 아니므로 gcd(15, 30 % 15) = gcd(15, 0) 호출
- gcd(15, 0) → b가 0이므로 a인 15를 반환
이처럼 재귀 호출이 반복되며 나머지가 점점 작아지다가 0이 되면, 마지막 남은 값이 바로 두 수의 최대공약수가 됩니다. 유클리드 호제법은 구현이 간단하면서도 계산 속도가 매우 빠르기 때문에, 최대공약수를 구하는 가장 대표적인 알고리즘으로 널리 사용되고 있습니다.