최대공약수(Greatest Common Divisor, GCD)란 두 수를 모두 나누어 떨어지게 하는 수 중 가장 큰 수를 의미합니다.
예를 들어, 두 수 63과 42가 있다고 가정해 보겠습니다.
63 = 7 * 3 * 3 42 = 7 * 3 * 2 따라서 63과 42의 GCD는 21입니다.
이번 글에서는 재귀(recursion)를 이용하여 두 수의 최대공약수를 구하는 C++ 프로그램을 소개합니다.
방법 1: 뺄셈을 이용한 재귀
#include<iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
}
int main() {
int a = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}출력 결과
GCD of 63 and 42 is 21
동작 원리
위 프로그램에서 gcd()는 재귀 함수이며, 매개변수로 a와 b 두 개를 받습니다. 동작 방식은 다음과 같습니다.
a또는b가 0이면 함수는 0을 반환합니다.a와b가 서로 같으면a를 반환합니다.a가b보다 크면a-b와b를 인자로 하여 자기 자신을 재귀적으로 호출합니다.b가a보다 크면a와b-a를 인자로 하여 자기 자신을 재귀적으로 호출합니다.
핵심 로직은 아래 코드 조각과 같습니다.
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
}방법 2: 유클리드 호제법(나머지 연산)을 이용한 재귀
재귀를 사용해 GCD를 구하는 또 다른 방법은 나머지 연산자(%)를 활용하는 것입니다. 이 방식은 일반적으로 뺄셈 방식보다 훨씬 빠르게 수렴합니다.
#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 = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
}출력 결과
GCD of 63 and 42 is 21
동작 원리
위 프로그램에서도 gcd()는 재귀 함수이며, 매개변수 a와 b를 받습니다. 만약 b가 0이라면 a를 main() 함수로 반환하고, 그렇지 않으면 b와 a % b(a를 b로 나눈 나머지)를 인자로 하여 자기 자신을 다시 호출합니다. 이 과정을 반복하다 보면 b가 0이 되는 순간의 a 값이 곧 최대공약수가 됩니다.
핵심 로직은 아래 코드 조각으로 확인할 수 있습니다.
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}마무리
두 방법 모두 재귀 호출을 통해 GCD를 구하지만, 나머지 연산을 사용하는 유클리드 호제법이 반복 횟수가 적어 실행 속도 면에서 더 유리합니다. 입력값이 커질수록 그 차이가 더욱 두드러지므로, 실제 개발에서는 방법 2를 사용하는 것이 권장됩니다.