유클리드 호제법

유클리드 호제법

두 수의 최대공약수(GCD)를 찾기 위한 알고리즘이다.

큰 수(a)를 작은 수(b)로 나누면서 나머지를 구하고, 그 나머지가 0이 될때까지 작은수(a)와 그 나눈 나머지(b)를 다시 나눈다. 나눈 나머지가 0이 된다면 a가 GCD가 된다.

💡 그러나 두 수의 순서에 영향을 받지 않으니 꼭 a에 큰 수, b에 작은 수를 넘겨야하는건 아니다.
Math.max, Math.min을 사용하여 구분지어 넘겨주는 이 연산이 오히려 성능을 소폭 떨어뜨릴 수 있다.

증명 :

getGCD(2, 10); // 2가 작음
// a=2, b=10
// temp = 2 % 10 = 2
// a = 10, b = 2
// temp = 10 % 2 = 0
// 종료 → GCD는 2
getGCD(10, 2); // 10이 큼
// a=10, b=2
// temp = 10 % 2 = 0
// 종료 → GCD는 2

결과는 동일

최대공약수(GCD) & 최소공배수(LCM)

💡 유클리드 호제법 알고리즘을 기반으로 최대공약수를 구하고 이를 기반으로 최소공배수를 구하면 된다.

최대공약수(GCD)

앞서 말한 유클리드 호제법 이용
b가 0이라면 a가 최대공약수가 되며, 그렇지 않으면 b와 a % b 둘로 다시 계산을 시작합니다.

1. 재귀

public static int getGCD(int a, int b){
        if (b == 0){
            return a;
        }

        return getGCD2(b, a % b);
    }

2. 반복문

public static int getGCD(int a, int b){
        while (b != 0){
            int tmp = a % b;
            a = b;
            b = tmp;
        }

        return a;
    }

최소공배수(LCM)

최소 공배수는 두 수의 곱에 두 수의 최대 공약수를 나눈 값과 같습니다.

public static int getLCM(int a, int b) {
    return a * b / gcd(a, b);
}

여러 수의 GCD & LCM 구하기

여러 수의 GCD

int[] array 파라미터로 받은 배열을 순회하면서 배열에 있는 모든 수의 최대공약수를 구함

public static int getGCD(int[] array) {
    int result = array[0];
    for (int i = 1; i < array.length; i++) {
        result = getGCD(result, array[i]);
    }
    return result;
}

public static int getGCD(int a, int b) {
    if (b == 0) {
    	return a;
    }
    return getGCD(b, a % b);
}

여러 수의 LCM

int[] array 파라미터로 받은 배열을 순회하면서 배열에 있는 모든 수의 최소공배수를 구함

public static int getLCM(int[] array) {
    int result = array[0];
    for (int i = 1; i < array.length; i++) {
        result = getLCM(result, array[i]);
    }
    return result;
}

public static int getLCM(int a, int b) {
    return (a * b) / getGCD(a, b);
}

관련된 백준 문제
https://velog.io/@seha01130/백준JAVA-9613번-GCD-합