두 수의 최대공약수(GCD) 구하기 – 유클리드 호제법으로 쉽게 배우기

수학에서 최대공약수(Greatest Common Divisor, GCD)란 두 정수를 모두 나누어 떨어지게 만들 수 있는 가장 큰 정수를 의미합니다. 단, 여기서 다루는 두 수는 반드시 0이 아니어야 한다는 조건이 있습니다.

이 글에서는 고전적인 방법인 유클리드 호제법(Euclidean Algorithm)을 이용해 두 수의 GCD를 구하는 과정을 알고리즘과 실제 코드 예제를 통해 살펴보겠습니다.

입력 및 출력 예시

입력:
두 수 51과 34
출력:
최대공약수(GCD): 17

51과 34를 동시에 나눌 수 있는 가장 큰 수가 17이므로, 두 수의 GCD는 17입니다.

알고리즘 개요

유클리드 호제법은 두 수의 차이를 이용해 문제를 점점 작은 크기로 줄여가며 답을 찾는 재귀적 방식입니다. 핵심 아이디어는 다음과 같습니다.

두 수 중 하나라도 0이면 GCD는 0입니다.
두 수가 같다면 그 값 자체가 GCD입니다.
두 수가 다르다면, 큰 수에서 작은 수를 뺀 값과 작은 수의 GCD를 다시 구하면 됩니다.

findGCD(a, b)

입력: 두 수 a와 b

출력: a와 b의 최대공약수

Begin
    if a = 0 OR b = 0, then
        return 0
    if a = b, then
        return b
    if a > b, then
        return findGCD(a-b, b)
    else
        return findGCD(a, b-a)
End

C++ 구현 예제

위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.

#include<iostream>
using namespace std;

int findGCD(int a, int b) {    // a가 b보다 크다고 가정
    if(a == 0 || b == 0)
        return 0;              // 두 수 중 하나가 0이면 최대공약수도 0
    if(a == b)
        return b;              // 두 수가 같으면 그 값이 곧 GCD
    if(a > b)
        return findGCD(a-b, b);   // 큰 수에서 작은 수를 빼며 재귀 호출
    else
        return findGCD(a, b-a);
}

int main() {
    int a, b;
    cout << "GCD를 구할 두 수를 입력하세요: "; cin >> a >> b;
    cout << "최대공약수(GCD): " << findGCD(a,b);
}

실행 결과

GCD를 구할 두 수를 입력하세요: 51 34
최대공약수(GCD): 17

동작 원리 살펴보기

입력값 51과 34가 주어졌을 때 함수의 실행 흐름은 다음과 같습니다.

findGCD(51, 34) → 51 > 34이므로 findGCD(17, 34) 호출
findGCD(17, 34) → 34 > 17이므로 findGCD(17, 17) 호출
findGCD(17, 17) → 두 수가 같으므로 17 반환

이처럼 유클리드 호제법은 매 단계마다 두 수의 차이로 문제를 축소해 나가기 때문에, 비교적 간단한 코드로도 효율적으로 최대공약수를 구할 수 있습니다.