최대공약수 구하기

최대공약수(GCD, Greatest Common Divisor)

최대공약수란 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

알고리즘 문제에서 두 수 혹은 집합 내 N개의 수의 최대공약수(GCD) 혹은 최소공배수(LCM) 구하기, 분수의 약분(기약 분수) 혹은 수학적 성질을 바탕으로 문제를 해결하는 형태로 등장하며, 문제를 효율적으로 풀기 위해 일반적으로 유클리드 호제법과 같은 알고리즘을 활용하게 된다.

대표적인 최대공약수 알고리즘

• 유클리드 호제법
• 확장된 유클리드 호제법

브루트 포스(Brute-Force)

두 수의 모든 공약수를 확인한 후, 그 중 가장 큰 값을 반환한다.

구현

function gcd(a, b){
    let cd = 0;
 
    for(let i = 1; i <= Math.min(a, b); i++){
        if(a % i === 0 && b % i === 0){
            cd = i;
        }
    }
 
    return cd;
}

의사코드(pseudo code)

• 최대공약수를 저장할 변수를 생성하고, 초기값으로 0을 설정한다.

• i를 1부터 a와 b 중 작은 값까지 1씩 증가시키며 반복한다.

  • 만약 a를 i로 나눈 나머지가 0이고, b를 i로 나눈 나머지도 0이라면,
    • gcd를 i로 변경한다.

• gcd를 리턴한다.

브루트 포스 방법은 두 양의 정수 a, b (a > b)에 대하여 1부터 b까지의 정수를 검사하여, 두 수 모두와 나누어 떨어지는 약수 중 가장 큰 값을 반환한다.

시간 복잡도는 O(b)로, 입력값이 10^9와 같은 큰 수일 경우 알고리즘 문제에서는 활용하기 어렵다.

유클리드 호제법(-互除法, Euclidean Algorithm)

두 양의 정수 a, b (a > b)에 대하여 a = bq + r (0 ≤ r < b)이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, r)

r = 0 이라면, a, b의 최대공약수는 b가 된다.

구현 - 재귀(Recursion)

function gcd(a, b){
    return b ? gcd(b, a % b) : a;
}

구현 - 반복문(while statement)

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

임시 변수를 선언하는 대신 구조 분해 할당으로 값을 교환하도록 작성할 수 있다. 코드의 간결성과 가독성을 높일 수 있지만, 불필요한 배열 생성 비용과 GC(Garbage Collection) 비용을 초래할 수 있다.

function gcd(a, b) {
    while(b) {
        [a, b] = [b, a % b];
    }
    return a;
}

의사코드(pseudo code)

• 나머지를 저장할 변수 c를 선언한다.

• b > 0인 동안 반복한다.

  • a를 b로 나눈 나머지를 c에 저장한다.
  • a를 b로 변경한다.
  • b를 c로 변경한다.

• a를 리턴한다.

유클리드 호제법 또는 유클리드 알고리즘은 두 양의 정수 a, b (a > b)에 대하여 두 수의 최대공약수는 큰 수(a)를 작은 수(b)로 나눈 나머지(r)와 작은 수(b) 사이의 최대공약수와 같다는 성질을 기반으로, b가 0이 될 때까지 r를 구하며, a를 b로, b를 r로 반복적으로 갱신하여 최대공약수를 구한다.

시간 복잡도는 O(log b)로, 매 실행마다 큰 수(a)의 크기가 절반 이상 줄어들기 때문에 입력값이 큰 경우에도 빠르고, 효율적으로 동작한다.

[TODO] 확장된 유클리드 호제법(Extended Euclidean Algorithm)