유클리드 호제법으로 최대공약수 구하기

코딩 테스트를 준비하다 보면 최대공약수(GCD)를 구해야 하는 문제를 자주 만나게 됩니다. 오늘은 가장 효율적인 방법인 유클리드 호제법에 대해 알아보겠습니다.

유클리드 호제법이란?

유클리드 호제법(Euclidean Algorithm)은 기원전 300년경 고대 그리스 수학자 유클리드가 발견한 알고리즘으로, 두 수의 최대공약수를 빠르게 구하는 방법입니다.

핵심 원리

두 수의 최대공약수는 작은 수와 나머지의 최대공약수와 같다

수식으로 표현하면:

GCD(a, b) = GCD(b, a % b)

동작 과정 예시

48과 18의 최대공약수를 구해봅시다.

1단계: GCD(48, 18)
48 = 18 × 2 + 12
→ GCD(18, 12)

2단계: GCD(18, 12)
18 = 12 × 1 + 6
→ GCD(12, 6)

3단계: GCD(12, 6)
12 = 6 × 2 + 0
→ GCD(6, 0)

나머지가 0이 되면 종료!
답: 6

JavaScript 구현

재귀 방식 (추천)

function gcd(a, b) {
    if (b === 0) return a;
    return gcd(b, a % b);
}

console.log(gcd(48, 18));  // 6
console.log(gcd(12, 8));   // 4

반복문 방식

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

화살표 함수로 간결하게

const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);

왜 효율적일까?

일반적인 방법과 비교해보면 차이가 확연합니다.

방법 1: 1부터 모든 수 확인 (비효율적)

// 시간 복잡도: O(min(a, b))
function gcdSlow(a, b) {
    let result = 1;
    for (let i = 1; i <= Math.min(a, b); i++) {
        if (a % i === 0 && b % i === 0) {
            result = i;
        }
    }
    return result;
}

방법 2: 유클리드 호제법 (효율적)

// 시간 복잡도: O(log(min(a, b)))
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);

큰 수일수록 성능 차이가 엄청납니다!

실전 활용: 분수의 약분

코딩 테스트에서 자주 나오는 분수 문제에 활용할 수 있습니다.

function solution(numer1, denom1, numer2, denom2) {
    // GCD 함수
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    
    // 두 분수 더하기: a/b + c/d = (ad + bc) / bd
    let numer = numer1 * denom2 + numer2 * denom1;
    let denom = denom1 * denom2;
    
    // 최대공약수로 약분
    let g = gcd(numer, denom);
    
    return [numer / g, denom / g];
}

console.log(solution(1, 2, 1, 3));  // [5, 6]

정리

• 유클리드 호제법은 최대공약수를 구하는 가장 효율적인 알고리즘입니다
• 나머지 연산을 반복하다가 나머지가 0이 되면 그때의 나누는 수가 답입니다
• 코딩 테스트에서 분수, 약분, 최소공배수 문제에 자주 사용됩니다
• 재귀로 구현하면 코드가 매우 간결합니다