C++에서 GCD(최대공약수) 구하기: 스타인 알고리즘 완벽 가이드

스타인 알고리즘(Stein's Algorithm), 흔히 이진 GCD 알고리즘이라고도 불리는 이 방법은 두 개의 음이 아닌 정수에 대한 최대공약수(GCD, Greatest Common Divisor)를 구하는 데 사용되는 효율적인 알고리즘입니다.

이 알고리즘의 가장 큰 특징은 전통적인 유클리드 호제법처럼 나눗셈을 사용하지 않고, 비트 시프트(bitwise shift), 비교, 뺄셈 연산만으로 최대공약수를 계산한다는 점입니다. 컴퓨터에서 비트 연산은 나눗셈보다 훨씬 빠르게 처리되기 때문에 성능 면에서 큰 이점을 얻을 수 있습니다.

기본 규칙은 간단합니다. 만약 두 수 a와 b가 모두 0이라면 gcd는 0입니다. 즉, gcd(0, 0) = 0 입니다.

알고리즘 동작 원리

시작
    1단계: a와 b가 모두 0이면 gcd는 0이다. → gcd(0, 0) = 0
    2단계: 모든 수는 0을 나눌 수 있으므로 → gcd(a, 0) = a, gcd(0, b) = b
    3단계: a와 b가 모두 짝수라면 → gcd(a, b) = 2 * gcd(a/2, b/2)
           (2가 공약수이므로. 2를 곱하는 것은 비트 시프트 연산자로 처리 가능)
    4단계: a가 짝수이고 b가 홀수라면 → gcd(a, b) = gcd(a/2, b)
           반대로 a가 홀수이고 b가 짝수라면 → gcd(a, b) = gcd(a, b/2)
           (2가 공약수가 아니기 때문)
    5단계: a와 b가 모두 홀수라면 → gcd(a, b) = gcd(|a-b|/2, b)
           (두 홀수의 차는 항상 짝수라는 점에 유의)
    6단계: a = b가 되거나 a = 0이 될 때까지 3~5단계를 반복한다.
종료

C++ 구현 예제

위 알고리즘을 바탕으로 두 수의 GCD를 계산하는 C++ 코드는 다음과 같이 작성할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
int funGCD(int x, int y){
    if (x == 0)
        return y;
    if (y == 0)
        return x;
    int k;
    for (k = 0; ((x | y) && 1) == 0; ++k){
        x >>= 1;
        y >>= 1;
    }
    while ((x > 1) == 0)
        x >>= 1;
    do {
        while ((y > 1) == 0)
            y >>= 1;
            if (x > y)
                swap(x, y); // u와 v를 교환
            y = (y - x);
    }
    while (y != 0);
        return x << k;
}
int main(){
    int a = 24, b = 18;
    printf("Calculated GCD of numbers (24,18) is= %d\n", funGCD(a, b));
    return 0;
}

실행 결과

위 코드를 실행하면 스타인 알고리즘을 적용하여 주어진 두 수 24와 18의 최대공약수가 다음과 같이 6으로 계산됩니다.

Calculated GCD of numbers (24,18) is= 6

마무리

스타인 알고리즘은 나눗셈 연산을 배제하고 비트 시프트와 뺄셈만 활용하기 때문에, 특히 임베디드 시스템처럼 나눗셈 연산 비용이 큰 환경에서 매우 유용합니다. 재귀 호출을 사용하지 않고 반복문으로 구현할 수 있다는 점도 실무에서 장점으로 꼽힙니다.