[알고리즘] GCD 최대공약수, LCM 최소공배수

오늘은 최대공약수 알고리즘을 구현 및 사용하는 방법에 대해 알아보자!

GCD는 Greatest Common Divisor로 최대 공약수이다. 

최대공약수는 두 수의 공통 약수중 최댓값을 말합니다. (약수는 나누어서 0 이 되는 수를 말한다) 이렇게 나누어서 0 이 되는 수중 공통적으로 들어가 있으며, 최댓값을 찾는 것입니다. 자바에서는 BigInteger 클래스에 최대공약수를 구할 수 있는 gcd() 함수를 제공합니다. 함수를 이용해서 구하는 방법과 직접 함수를 만드는 방법에 대해 알아 본다.

1. BigInteger 내장 함수를 사용

private static int gcdThing(int a, int b) {

        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        
        return gcd.intValue();
    }

2. 직접 구현

gcd 함수를 직접 구현하는 방법은 호제법을 이용한 방법이다. 
호제법이 두수를 나누어서 나온 나머지를 이전 나머지에 다시 나누고, 그렇게 0 이 나올 때까지 반복한 후 중지한다. 중지했을 때, 바로 직전의 나머지가 최대공약수가 되는 것이다. 

예를 들어 192와와 72의의 최대공약수를 구한다고 합시다. 아래 처럼 3번째 단계가 되면 나머지가 0 이죠. 그때 이전 몫인 24가 최대공약수가 되는 것입니다.

1. 192 = 72 x 2 + 48

2. 72 = 48 x 1 + 24

3. 48 = 24 x 2 + 0

이 호제법을 이용해서 직접 gcd 구현하는 방법에는 두 가지가 있다.

(1) 재귀 문을 이용

private static int gcd(int a, int b){
        if(b == 0) return a;
        return gcd(b, a % b);
    }

(2) 반복문을 이용

private static int gcd(int a, int b) {
        int tmp, n;

        //a에 큰 값을 위치시키기 위한 조건이다.
        if (a < b) {
            tmp = a;
            a = b;
            b = tmp;
        }

        //b가 0 될때까지(a%b), 반복문을 돌게되고, b가 0인 순간의 a를 GCD로 판단하고 리턴한다
        while (b != 0) {
            n = a % b;
            a = b;
            b = n;
        }
        return a;
    }

 

같은 기능을 수행하기 때문에 코드의 간결성을 위해서 BigInteger의 내장 함수 혹은 재귀 문을 이용하여 직접 구현하는 방법이 효율적이라고 판단된다. 

 

최소 공배수의 경우 두 수를 곱하고 그 값에 최대공약수를 단순히 나눠주면 구할 수 있다. 

최소공배수 LCM (Least Common Multiple)는 gcd() 함수를 이용하여 간단하게 구할 수 있다.

    public static int lcm(int x, int y) {

        //0이 아닌 두 수의 곱 / 두 수의 최대공약수
        return (x * y) / gcd(x, y);
    }