[알고리즘] 유클리드 호제법

유클리드 호제법

• 이 문제를 풀기 위해 최대공약수와 최소공배수가 필요했다. 두 수의 최대 공약수를 구하는 기본적인 방법은 소인수분해를 한 뒤 공통부분을 찾는 것이다. 하지만 이렇게 하면 시간 복잡도가 O(n)이 된다. 또한 알고리즘으로 소인수분해를 구현하는 거 또한 간편하지 않다.
• 유클리드 호제법이란 두 수의 최대공약수를 쉽게 구할 수 있는 방법으로 시간 복잡도를 줄여 간편하면서도 효율적인 알고리즘이다.

두 수의 최대공약수 찾는 법

• 유클리드 호제법은 (a, b) 두 수가 있을 때 a를 b로 나눈 나머지가 0이 아니라면 b에 나머지를 넣고 a에 원래 b에 있던 값을 넣어 나머지가 0이 될 때까지 구하는 방법이다. 즉 (a, b) a%b=r 일때 (a,b) , (b, r) 두 개의 최대공약수는 같다는 것이다. 시간복잡도는 O(logn)이 된다.

예시

• 168과 132의 최대 공약수를 구하면 168 = 136 * 1 + 36  =>  132 = 36 * 3 + 24  => 36 = 24 * 1 + 12  => 24 = 12 * 2  (168,132)는 (24,12)와 공통된 최대공약수를 갖는다. 고로 (168,132)의 최대공약수는 12이다.

소스코드

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

최소공배수

- 최대공약수를 유클리드 호제법을 이용해 구했다면 최소공배수는 쉽게 구 할 수 있다. (168,132)의 최대 공약수는 12라는 것을 알았다. 최소공배수는 168과 132를 곱해준 뒤 최대공약수인 12로 나눠주기만 하면 된다. 두 수의 최소공배수는 '1848'이 된다.