[알고리즘] 최대공약수(GCD)와 유클리드 호제법(Euclidean algorithm)

최대공약수(GCD), 최소공배수(LCM) 구하는 법

최대공약수(GCD, Greatest Common Divisor)는 두 자연수의 공통된 약수 중에서 가장 큰 수를 의미하며, 최소공배수(LCM, Least Common Muliple)는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.

 

최대공약수는 두 자연수를 나누어 떨어지게 하는 최댓값을 찾으면 되며, 최소공배수는 두 자연수를 곱하고 GCD만큼 나눠주면 된다. 이를 코드로 구현하면 다음과 같다.

// 시간복잡도 O(N)
int gcd(int a, int b){
    int res = 0;
    for(int i = 1; i <= min(a, b); i++){
        if(a % i == 0 && b % i == 0) res = i;
    }
    return res;
}

// 시간복잡도 O(N)
int LCM(int a, int b){
    return a * b / gcd(a, b);
}

 

N개의 자연수의 최대공약수를 구하고 싶은 경우

2개의 자연수에 대한 최대공약수가 아닌 N개의 자연수에 대한 최대공약수를 구하고 싶은 경우에는 이미 구한 최대공약수와 다른 수와의 최대공약수를 구하는 과정을 반복하면 된다. 왜냐하면 N개의 자연수의 최대공약수를 A, M개의 자연수의 최대 공약수를 B라고 가정했을 때(M < N), 항상 B = A * X이기 때문이다. 즉, B에 존재하지 않는 약수가 A에 존재할 가능성이 없기 때문에, B에서 존재하지 않는 약수가 없어도 A를 구하는데 전혀 상관없다. 코드로 구현하면 다음과 같다.

// 시간 복잡도 O(N^2)
int gcd_n(vector<int>& v1) {
    int res = v1[0];
    for(int i = 1; i < v1.size(); i++){
        res = gcd(result, v1[i]);
    }
    return res;
}

 

최적화를 할 수는 없을까?

N개의 자연수의 최대공약수를 구하게 될 경우, 배열을 선형 탐색하는 과정에서 N번, 두 수에 대한 gcd를 구하는 과정에서 N번 반복하여 결론적으로 O(N^2)의 시간복잡도를 가지게된다. 하지만 여기서 유클리드 호제법을 활용하면 gcd를 구하는 과정의 시간복잡도가 O(N) -> O(logN)으로 줄어들어 전체 알고리즘의 시간복잡도가 O(N^2) -> O(NlogN)으로 최적화가 가능하다. 

 

유클리드 호제법이란?

유클리드 호제법은 유클리드의 원록에 적혀있는 내용으로, 아래와 같은 내용을 담고 있다.(추가로, 호제법의 '호' 는 서로, '제'는 나눈다는 뜻으로, 두 자연수가 서로 나누기 때문에 붙여진 이름이다.)

두 양의 정수 a, b (a > b)에 대하여 a = bq + r (0 <= r < b)라 하면, a, b의 최대공약수는 b,r의 최대공약수와 같다. 즉,            
                                                                             gcd(a,b) = gcd(b,r)
r = 0이라면, a, b의 최대공약수는 b가 된다.

 

위의 글을 다르게 말하면 a, b의 최대공약수는 b와 나머지의 최대공약수와 같다는 뜻이다.

유클리드 호제법의 위 성질을 이용해 도출한 결과물을 다시 유클리드 호제법의 입력값으로 넣을 수 있는데, 이를 나머지인 r이 0이 될 때까지 반복해 a, b의 최대공약수를 구할 수 있다.(나머지가 없는 경우 a, b중 작은 값이 최대공약수이기 때문)

 

유클리드 호제법을 증명하는 법을 알고 싶다면, 아래 링크에 연결된 나무위키를 보면된다. 

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95#s-2

유클리드 호제법

 

동작방식

1. 최대공약수를 구할 두 자연수 A, B를 준비한다. 예시에선 A는 42, B는 24를 준비했다.

 

A = 42, B = 24

 

2. A % B를 통해 나머지 r을 구한 다음, gcd(a,b)이였던 상황을 gcd(b,r)로 변경한다.

 

r = 42 % 24 = 18

 gcd(b, r) = gcd(24, 18)

 

3. r이 0이 될때까지 2번 과정을 반복하고, r이 0이 되었을 때 B값으로 gcd(A, B)의 최대공약수를 구한다.

 

42 = 24 * 1 + 18,  gcd(42, 24) = gcd(24, 18)

24 = 18 * 1 + 6,  gcd(24, 18) = gcd(18, 6)

18 = 6 * 3 + 0,  gcd(18, 6) = gcd(6, 0)

∴  gcd(42, 24) = 6

 

구현 코드(유클리드 호제법을 이용한 GCD)

// 시간복잡도 O(logN)
int gcd(int a, int b) {
    while (b != 0) {
        int r = b;
        b = a % b;
        a = r;
    }
    return a;
}

 

 

짚고 넘어가야 할 점

유클리드 호제법을 이용한 GCD를 구할 때 A > B를 지킬 필요는 없다.

손으로 계산할 때는 A가 B보다 커야하지만 코드로 나타낼 때는 신경쓰지 않아도 된다. 왜냐하면 A < B인 경우, a % b == a이기 때문에 gcd(a,b)이 gcd(b,a)로 자동으로 크기 정렬이 된다. 위의 예시를 통해 보여주자면 다음과 같다.

 

24 = 42 * 0 + 24,  gcd(24, 42) = gcd(42, 24)

42 = 24 * 1 + 18,  gcd(42, 24) = gcd(24, 18)

.

.

.

∴  gcd(24, 42) = 6

참고자료

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

https://heoseongh.github.io/algorithm/Euclidean/