유클리드 호제법

두 정수의 최대공약수(GCD)를 "큰 수를 작은 수로 나눈 나머지"를 반복해서 구하는 알고리즘입니다.

동작 과정

gcd(48, 18) 구하기

48 = 18 × 2 + 12   → gcd(48, 18) = gcd(18, 12)
18 = 12 × 1 + 6    → gcd(18, 12) = gcd(12, 6)
12 = 6  × 2 + 0    → gcd(12, 6)  = gcd(6, 0)

나머지가 0이 되면 그때의 나누는 수가 최대공약수

결과: gcd(48, 18) = 6

나머지가 0이 될 때까지 "(나누는 수, 나머지)" 쌍으로 문제를 계속 축소합니다. gcd(a, b) = gcd(b, a % b)가 성립하기 때문입니다 — a를 b로 나눈 나머지 r은 a와 b의 공약수를 그대로 공약수로 가지므로, (a, b)의 최대공약수와 (b, r)의 최대공약수는 항상 같습니다.

구현

// 재귀
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 반복
int gcdIter(int a, int b) {
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

// 최소공배수(LCM)는 GCD로부터 바로 유도된다
long lcm(int a, int b) {
    return (long) a / gcd(a, b) * b;
}

복잡도

나머지를 취하는 연산마다 두 수 중 작은 쪽이 최소 절반 이하로 줄어들기 때문에(최악의 경우에도 피보나치 수열만큼 느리게 감소) 반복 횟수가 로그 수준으로 보장됩니다.

주의사항

• 입력이 (0, n) 인 경우: gcd(0, n) = n이 정상 동작이다. 재귀/반복 구현 모두 b == 0을 종료 조건으로 두면 자연스럽게 처리된다
• 음수 입력: 수학적으로 최대공약수는 항상 양수다. 음수가 들어올 수 있다면 Math.abs로 먼저 정규화한다
• LCM 오버플로: a * b를 먼저 계산하면 int 범위를 넘기 쉽다. a / gcd(a, b) * b 순서로 나눗셈을 먼저 해 오버플로를 피한다
• 최대공약수와 최소공배수뿐 아니라, 분수 약분이나 두 수가 서로소(coprime, gcd = 1)인지 판별할 때도 그대로 쓰인다

핵심 정리

• gcd(a, b) = gcd(b, a % b), b == 0이면 종료
• 나머지 연산 한 번마다 값이 로그 수준으로 줄어 O(log(min(a, b)))
• LCM = a / gcd(a, b) * b (오버플로 방지 순서)
• 계수까지 함께 구해야 한다면 확장 유클리드 호제법으로 확장할 수 있다