C++에서 유클리드 알고리즘과 재귀 호출 없이 두 수의 최대공약수(HCF) 구하기

최대공약수(HCF, GCD)는 일반적으로 유클리드 호제법(Euclidean Algorithm)을 사용하면 매우 쉽게 계산할 수 있습니다. 하지만 이번 글에서는 유클리드 알고리즘도, 재귀 함수도 사용하지 않고 두 수의 최대공약수를 구하는 방법을 알아보겠습니다.

예를 들어 16과 24라는 두 수가 주어졌을 때, 이 두 수의 최대공약수는 8입니다.

접근 방식

핵심 아이디어는 단순한 반복문 탐색입니다. 로직은 다음과 같습니다.

1. 두 수 중 더 작은 값(min)을 구합니다.
2. 만약 작은 값이 두 수를 모두 나누어 떨어뜨린다면, 그 값이 곧 최대공약수입니다.
3. 나누어 떨어지지 않는다면, min / 2부터 2까지 값을 하나씩 줄여가며 현재 값이 두 수를 모두 나눌 수 있는지 확인합니다.
4. 조건을 만족하는 첫 번째 값이 최대공약수이며, 끝까지 찾지 못하면 최대공약수는 1입니다.

내림차순으로 탐색하기 때문에 조건을 만족하는 가장 큰 공약수를 먼저 발견하게 되므로, 별도의 정렬이나 추가 연산 없이 정확한 결과를 얻을 수 있습니다.

예제 코드

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    int min_num = min(a, b);
    // 작은 수가 두 수를 모두 나누면 그것이 바로 최대공약수
    if (a % min_num == 0 && b % min_num == 0)
        return min_num;
    // min/2부터 2까지 내림차순으로 공약수 탐색
    for (int i = min_num / 2; i >= 2; i--) {
        if (a % i == 0 && b % i == 0)
            return i;
    }
    // 공약수를 찾지 못한 경우 1 반환
    return 1;
}

int main() {
    int a = 16, b = 24;
    cout << "HCF: " << gcd(a, b);
}

실행 결과

HCF: 8

시간 복잡도

이 방법은 최악의 경우 작은 수의 절반까지 전부 확인해야 하므로 시간 복잡도는 O(min(a, b))입니다. 유클리드 호제법(O(log n))에 비해 느리지만, 알고리즘의 동작 원리가 직관적이고 재귀 호출로 인한 스택 오버플로우 걱정이 없다는 장점이 있습니다. 학습 목적으로 최대공약수의 개념을 이해하는 데 유용한 방법입니다.