유클리드 호제법을 이용한 최대공약수 구하기 - Java

유클리드 호제법이란?

유클리드 호제법은 알고리즘 기초 문제 중 하나인 최대공약수 구하기를 해결하기 위한 방법 중 하나로 적은 연산으로도 최대공약수를 구할 수 있다. 여기서 호제법이란 두 수가 서로를 나누어 원하는 수를 얻는 알고리즘을 나타낸다. 이때 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 

예를 들어, 99와 57의 최대공약수를 유클리드 호제법을 이용하여 구한다면, 다음과 같다.

 

99 % 57 = 42 → 나머지(42) != 0

57 % 42 = 15 → 나머지(15) != 0

42 % 15 = 12 → 나머지(12) != 0

15 % 12 = 3 → 나머지(3) != 0

12 % 3 = 0 → 나머지(0) == 0 → 작업 종료

 

최종적으로 99와 57의 최대공약수는 12와 3의 최대공약수인 3과 같게 된다.

 

소스코드 구현 및 성능 비교

유클리드 호제법을 이용하여 최대공약수를 구하는 로직을 자바로 구현하면 다음과 같다.

 

import java.util.*;

class Main {

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

        return a;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        System.out.println(getGcd(a, b));
        System.out.println((a * b) / getGcd(a, b)); // 참고 : a * b = LCM(최소공배수) * GCD(최대공약수)
    }
}

 

이를 다음과 같이 간단하게 재귀로 나타낼 수도 있다.

 

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

 

하지만 두 수의 최대공약수를 구하기 위해 반드시 유클리드 호제법을 이용할 필요는 없다. 좀 더 직관적인 방법으로는 두 수 중 적은 숫자를 기준으로(a > b → b) 각각의 수(a, b)를 나누었을 때 나머지가 0이 나올때까지 1씩 감소시키는 것이다. 자바 소스코드로 나타내면 다음과 같다.

 

import java.util.*;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();

        for (int i = b; i >= 1; i--) { // a > b 가정
            if (a % i == 0 && b % i == 0) {
                System.out.print(i);
                break;
            }
        }
    }

}

 

하지만 위 알고리즘의 경우 시간 성능이 최선의 경우에는 운이 좋게 한번만에 연산이 끝날 수도 있지만 최악의 경우에는 1이 될때까지 연산이 계속될 수도 있는 단점이 있다.

 

아래 예시에서는 위 알고리즘을 통해 99와 57의 최대공약수를 구했더니 무려 55번의 연산 작업으로 정답을 구했다. 유클리드 호제법을 이용했을 경우 5번의 연산 작업으로 정답을 구한 것과 상당히 비교된다.

 

99 % 57 != 0 && 57 % 57 == 0 → false(불일치)

99 % 56 != 0 && 57 % 56 != 0 → false(불일치)

99 % 55 != 0 && 57 % 55 != 0 → false(불일치)

...

99 % 3 == 0 && 57 % 3 == 0 → true(일치)

 

 물론 운이 좋게 30과 10의 최대공약수를 구할 때는 한 번의 연산으로 최대공약수를 구할 수 있겠지만,(물론 유클리드 호제법을 이용한 경우에도 한 번의 연산으로 가능) 30과 11이라는 숫자가 주어진 경우 11번의 연산 작업을 해야 정답을 구할 수 있게 된다.

 

결론, 왠만하면 최대공약수를 구하는 알고리즘을 구할 때는 유클리드 호제법을 이용해보자!

 

 

참고 자료

• https://ko.wikipedia.org/wiki/유클리드_호제법