최근에 Codeforces 문제 풀이를 하다 최대 공약수 개념을 적용 시켜야 하는 문제가 있었다. (혹시나 궁금하신 분은 https://codeforces.com/contest/1920/problem/C 의 문제를 풀어보자) 이전부터 최대공약수를 구하는 방법 중 유클리드 호제법을 이용하면 보다 빠르게 구할 수 있다 정도만 알고 있었는데, 이번 포스팅에서는 최대공약수를 구하는 방법과 시간복잡도에 대해 정리해 보려 한다.
최대공약수 구하기
완전 탐색 (Bruteforce)
가장 먼저 최대공약수를 구하는 알고리즘으로는 브루트포스 알고리즘을 생각할 수 있을 것이다. 1부터 시작해서 두 수를 나눠보며, 나머지가 0인 경우 갱신하는 형태의 코드를 다음과 같이 작성할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
int gcd_naive(int a, int b) {
int smaller = a < b ? a : b;
int ret = 1;
for (int i = 1; i <= smaller; ++i) {
if (a % i == 0 && b % i == 0) {
ret = i;
}
}
return ret;
}
int main() {
printf("%d\n", gcd_naive(60, 48));
return 0;
}
굉장히 직관적이고 단순하며, 실행 결과도 잘 나오는 것을 확인할 수 있다.
하지만 실행 시간이 인자로 주어지는 수의 크기에 비례하기 때문에 억 단위 이상의 수에 대해서는 계산 시간이 느리다는 단점이 있다.
유클리드 호제법 (Euclidean algorithm)
위의 문제점을 해결하기 위해 사용하는 것이 바로 유클리드 호제법이다. 유클리드 호제법은 두 수 a, b의 최대공약수는 b와 a를 b로 나눈 나머지 즉, b, a%b의 최대공약수와 같다는 점을 이용한다. 이게 왜 되는가?에 대한 증명은 귀류법을 통해 증명할 수 있는데, 내용이 크게 어렵지 않고 블로그에서 많이 다루고 있으니 관심 있다면 한 번 찾아보면 좋을 것 같다.
유클리드 호제법을 재귀 함수를 이용하여 작성하면 아래와 같이 작성할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
int gcd_euc_recursive(int a, int b) {
// base case
if (b == 0) return a;
return gcd_euc_recursive(b, a % b);
}
int main() {
printf("%d\n", gcd_euc_recursive(60, 48));
return 0;
}
반복문을 이용하면 아래와 같이 작성할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
int gcd_euc_iterative(int a, int b) {
while (b != 0) {
int tmp = b;
b = a % b;
a = tmp;
}
return a;
}
int main() {
printf("%d\n", gcd_euc_iterative(60, 48));
return 0;
}
시간 복잡도
Bruteforce 방식은 작은 수 만큼 반복문을 돌면서 수행되기 때문에 gcd_naive의 시간복잡도는 O(min(a, b))임을 쉽게 알 수 있다. 그렇다면 유클리드 호제법의 시간복잡도는 어떻게 계산할까? 엄밀한 증명은 아니지만 아래와 같은 과정을 통해 gcd_euc_recursive, gcd_euc_iterative의 시간복잡도는 O(log(max(a, b))임을 알 수 있다.
두 수 a, b에 대해 a < b인 경우 앞서 작성한 gcd 코드에 따르면 결국 a와 b가 교체되므로, a ≥ b인 정수라고 가정하겠다. a≥b인 두 수에 대해,
i) a ≥ 2 * b인 경우
a를 b로 나눈 나머지 r은 0 ≤ r < b을 만족한다. 이 때 a ≥ 2 * b이므로, a / 2 ≥ b > r이 되므로 한번 유클리드 호제법을 적용한 후의 나머지는 a의 절반 미만임을 알 수 있다.
ii) 2 * b > a인 경우
a ≥ b라 가정했으므로, a를 b로 나눈 나머지 r은 a - b가 된다. (b는 a의 절반보다 크므로, 몫이 0 또는 1이 될 수 밖에 없는 상황) 0 ≤ r < b 에서 r = a - b 이고, 2 * b > a 이므로 r = a - b < a / 2 가 된다. 따라서 유클리드 호제법을 적용한 후의 나머지는 a의 절반 미만이 된다.
즉 어떠한 경우에도 유클리드 호제법을 적용한 후의 a는 절반 미만이 되므로, 시간복잡도는 O(log(a))가 된다.
*** 인터넷을 찾다보면 다음과 같이 시간복잡도가 O(log(max(a, b)), O(max(loga, logb)), O(min(loga, logb))등 다양한 형태로 표기되어 있는 것을 볼 수 있다. 개인적인 생각으로는 O(min(…))는 결국 한번 수행하고 나면 a, b 두 수 중 작은 값에 맞춰져서 수행되기 때문에 constant time으로 보고 저렇게 표현한게 아닐까? 싶다.
이진 유클리드 호제법
위는 반복적으로 modular 연산을 통해 최대공약수를 구했는데, 최적화에 진심인 분들은 아쉬운 부분이 있었을 것이다. % 연산은 다른 +, -, bit shift 연산에 비해 꽤나 CPU Cycle을 많이 잡아먹는 연산이다. 이러한 부분을 없애고자 두 수가 홀수, 짝수인 경우를 비교해 다음과 같이 분할 정복을 활용한 알고리즘도 활용할 수 있다. 자세한 내용은 아래 링크를 참고하자.
https://en.algorithmica.org/hpc/algorithms/gcd/
Bonus 내장 함수 __gcd
놀랍게도 최대공약수를 구하는 함수가 g++의 STL에 __gcc 함수로 구현되어 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* This is a helper function for the rotate algorithm specialized on RAIs.
* It returns the greatest common divisor of two integer values.
*/
template<typename _EuclideanRingElement>
_EuclideanRingElement
__gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
{
while (__n != 0)
{
_EuclideanRingElement __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
위에서 구현한 gcd_euc_iterative와 동일한 형태로, 프로그래밍 문제 풀이 중 필요하다면 구현하지 말고 바로 써먹도록 하자.
여러 수에 대한 최대공약수
위 내용에서는 두 수에 대한 최대공약수만을 다뤘는데, 만약 n개의 수에 대한 최대공약수를 구하는 경우는 시간복잡도가 어떻게 될까? 뭔가 O(n * log(N))일 것으로 보이지만 그렇지 않다고 한다. 마찬가지로 Codeforces 문제 풀이를 하면서 알게 되었는데 아래 링크를 참조하면 좋을 것 같다.