[알고리즘] Euclidean Algorithm : 유클리드 호제법으로 최대공약수(GCD)를 구해보자

유클리드 호제법 (Euclidean Algorithm) 

유클리드 호제법이라고도 불리는 유클리드 알고리즘은 둘 이상의 정수의 최대공약수(GCD)를 구하는 알고리즘이다.

 

유클리드 호제법은

큰 수(num1)와 작은 수(num2) 사이의 최대 공약수는 큰 수를 작은 수로 나눈 나머지(R)와 작은 수(num2) 사이의 최대 공약수와 같다는 점을 반복하여 문제를 해결한다.

 

기본적인 방법은 다음과 같다.

 

1. 큰 수(num1)에서 작은 수(num2)를 나눈다.
2. 나머지가 0이 아니라면, 나머지와 작은 수(num2)로 1번부터 다시 시작한다.
3.  1~ 2 과정을 반복해 나머지가 0이라면, 그 수가 최대 공약수이다.

 

예를 들어, 21과 49 가 있다. mod 연산을 진행하면,

49 mod 21 = 7

나머지가 0이 아니므로,  나머지인 7과 작은 수인 21로 mod 연산을 진행한다.

21 mod 7 = 0

 

나머지가 0이므로 21과 49의 최대 공약수는 7이다.

 

사실 알고리즘이라기 보단 간단한 수학 공식정도로 생각하면 될 정도로 간단하고, 가끔 알고리즘 문제에 활용할 일이 생기니, 읽어 두기만 해도 충분하다.

 

---

두 수 사이의 GCD, 최대 공약수 구하기 

일반적인 방법

일반적인 방법으로 두 정수 (252 ,105) 사이의 최대공약수, 즉 GCD (Greatest Common Divisor)를 구하여 보자.

 

252와 105는 일반적으로 보기에도 딱 떠오르지 않고, 소인수 분해 과정을 거쳐서 구하거나 완전탐색 방법으로 구할 수 있다. 완전 탐색 코드의 경우는 다음과 같다.

 

public class example {
    public static void main(String[] args) {
        int a = 252;
        int b = 105;

        for (int GCD = b; GCD > 0; GCD--) {
            if (b % GCD == 0 && a % GCD == 0) {
                System.out.println("GCD = " + GCD);
                break;
            }
        }
    }
}

GCD = 21

 

두 수중 작은 숫자인 105부터 1씩 차감해 가며 공약수인지를 구하고, 공약수면 그 값을 출력한다.

이렇게 하면 시간 복잡도는 O(n) 이 된다.

 

 

 

 

유클리드 호제법

유클리드 호제법의 경우, 재귀 또는 반복문을 활용하여 구현한다.

public class example {
    public static void main(String[] args) {
        int a = 252;
        int b = 105;

        System.out.println("GCD = " + gcd(252, 105));
    }

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

GCD = 21

유클리드 호제법 아이디어대로, 나머지와 작은 수를 재귀하여 gcd를 구하였다.

이 경우에는 시간 복잡도가 O(log min(a, b)) 으로 더 짧은 시간 안에 최대공약수를 구할 수 있다.

 

 

---

세 수 이상에서 GCD, 최대 공약수 구하기 

일반적인 방법

세 수 이상에서도 마찬가지로, 가장 작은 수를 기준으로 정말탐색하여 구할 수 있다.

public class example {
    public static void main(String[] args) {
        int a = 252;
        int b = 105;
        int c = 91;

        for (int GCD = c; GCD > 0; GCD--) {
            if (a % GCD == 0 && b % GCD == 0 && c % GCD == 0) {
                System.out.println("GCD = " + GCD);
                break;
            }
        }
    }
}

GCD = 7

 

 

 

유클리드 호제법

세 수에서는 두 수씩 유클리드를 사용하면 된다.

public class example {
    public static void main(String[] args) {
        int a = 252;
        int b = 105;
        int c = 91;

        System.out.println("GCD = " + gcd(252, gcd(105, 91)));
    }

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

GCD = 7

 

 

 

---

유클리드 예시문제

백준 골드 5 https://www.acmicpc.net/problem/21870

21870번: 시철이가 사랑한 GCD