최대공약수를 구하는 유클리드 알고리즘¶
두 음이 아닌 정수 $a$와 $b$가 주어질 때, 이들의 GCD(최대공약수), 즉 $a$와 $b$ 모두의 약수인 수 중 가장 큰 수를 구해야 합니다. 이는 흔히 $\gcd(a, b)$로 표기합니다. 수학적으로는 다음과 같이 정의합니다.
(여기서 기호 "$\mid$"는 나누어떨어짐을 나타냅니다. 즉, "$k \mid a$"는 "$k$가 $a$를 나눈다"는 뜻입니다)
두 수 중 하나가 0이고 다른 하나가 0이 아니면, 정의에 따라 두 수의 최대공약수는 0이 아닌 수입니다. 두 수가 모두 0이면 최대공약수가 정의되지 않지만(임의로 큰 어떤 수든 될 수 있습니다), $\gcd$의 결합법칙이 성립하도록 이 경우에도 0으로 정의하는 것이 편리합니다. 이로부터 간단한 규칙을 얻습니다. 두 수 중 하나가 0이면 최대공약수는 나머지 수입니다.
아래에서 설명할 유클리드 알고리즘을 사용하면 두 수 $a$와 $b$의 최대공약수를 $O(\log \min(a, b))$에 구할 수 있습니다. 이 함수는 결합법칙이 성립하므로, 세 개 이상의 수의 GCD를 구하려면 $\gcd(a, b, c) = \gcd(a, \gcd(b, c))$와 같은 방식으로 계속 계산하면 됩니다.
이 알고리즘은 유클리드의 "원론"(Elements, 직역하면 '원소')(기원전 300년경)에 처음 기술되었지만, 그보다 더 이전에 기원했을 가능성도 있습니다.
알고리즘¶
원래 유클리드 알고리즘은 다음과 같이 정식화되었습니다. 두 수 중 하나가 0이 될 때까지 큰 수에서 작은 수를 뺍니다. 실제로 $g$가 $a$와 $b$를 나누면 $a-b$도 나눕니다. 반대로 $g$가 $a-b$와 $b$를 나누면 $a = b + (a-b)$도 나누므로, $\{a, b\}$의 공약수 집합과 $\{b,a-b\}$의 공약수 집합은 일치합니다.
$a$에서 $b$를 최소 $\left\lfloor\frac{a}{b}\right\rfloor$번 뺄 때까지는 $a$가 계속 더 큰 수로 남는다는 점에 유의하십시오. 따라서 속도를 높이기 위해 $a-b$를 $a-\left\lfloor\frac{a}{b}\right\rfloor b = a \bmod b$로 대체합니다. 그러면 알고리즘을 매우 간단하게 정식화할 수 있습니다.
구현¶
int gcd (int a, int b) {
if (b == 0)
return a;
else
return gcd (b, a % b);
}
C++의 삼항 연산자를 사용하면 한 줄로 작성할 수 있습니다.
int gcd (int a, int b) {
return b ? gcd (b, a % b) : a;
}
마지막으로, 재귀를 사용하지 않는 구현은 다음과 같습니다.
int gcd (int a, int b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
C++17부터는 C++에 gcd가 표준 함수로 구현되어 있다는 점에 유의하십시오.
시간 복잡도¶
이 알고리즘의 실행 시간은 라메(Lamé)의 정리로 추정할 수 있습니다. 이 정리는 유클리드 알고리즘과 피보나치 수열 사이의 놀라운 연관성을 보여 줍니다.
$a > b \geq 1$이고 어떤 $n$에 대해 $b < F_n$이면, 유클리드 알고리즘은 재귀 호출을 최대 $n-2$번 수행합니다.
더 나아가, 이 정리의 상한이 최적임을 보일 수 있습니다. $a = F_n$이고 $b = F_{n-1}$이면 $gcd(a, b)$는 재귀 호출을 정확히 $n-2$번 수행합니다. 다시 말해, 연속한 피보나치 수는 유클리드 알고리즘의 최악의 경우 입력입니다.
피보나치 수는 지수적으로 증가하므로, 유클리드 알고리즘은 $O(\log \min(a, b))$에 동작함을 알 수 있습니다.
복잡도를 추정하는 또 다른 방법은 $a \geq b$인 경우 $a \bmod b$가 $a$보다 최소 $2$배 작다는 점에 주목하는 것입니다. 따라서 알고리즘을 한 번 반복할 때마다 큰 수가 최소 절반으로 줄어듭니다. 이 논리를 수의 집합 $a_1,\dots,a_n \leq C$의 GCD를 구하는 경우에 적용하면, 알고리즘의 자명하지 않은 반복마다 현재 GCD 후보가 최소 $2$배 줄어들므로 전체 실행 시간을 $O(n \log C)$가 아닌 $O(n + \log C)$로 추정할 수 있습니다.
최소공배수¶
최소공배수(흔히 LCM으로 표기합니다)의 계산은 다음의 간단한 공식을 이용하여 GCD의 계산으로 환원할 수 있습니다:
따라서 LCM은 유클리드 알고리즘을 사용하여 같은 시간 복잡도로 계산할 수 있습니다:
먼저 $a$를 GCD로 나누어 정수 오버플로를 교묘하게 피하는 구현의 예는 다음과 같습니다:
int lcm (int a, int b) {
return a / gcd(a, b) * b;
}
이진 GCD¶
이진 GCD 알고리즘은 일반적인 유클리드 알고리즘을 최적화한 것입니다.
일반적인 알고리즘에서 느린 부분은 나머지 연산입니다. 나머지 연산은 $O(1)$로 간주하기는 하지만, 덧셈, 뺄셈, 비트 연산과 같은 더 단순한 연산보다 훨씬 느립니다. 따라서 나머지 연산은 피하는 편이 좋습니다.
사실 나머지 연산을 사용하지 않는 빠른 GCD 알고리즘을 설계할 수 있습니다. 이 알고리즘은 몇 가지 성질에 기반합니다:
- 두 수가 모두 짝수이면, 두 수에서 각각 인수 2를 묶어 낸 뒤 남은 수들의 GCD를 계산할 수 있습니다: $\gcd(2a, 2b) = 2 \gcd(a, b)$.
- 한 수는 짝수이고 다른 수는 홀수이면, 짝수에서 인수 2를 제거할 수 있습니다: $b$가 홀수이면 $\gcd(2a, b) = \gcd(a, b)$입니다.
- 두 수가 모두 홀수이면, 한 수에서 다른 수를 빼도 GCD는 변하지 않습니다: $\gcd(a, b) = \gcd(b, a-b)$
이 성질들과 GCC의 빠른 비트 연산 함수 몇 가지만 사용하여 빠른 버전을 구현할 수 있습니다:
int gcd(int a, int b) {
if (!a || !b)
return a | b;
unsigned shift = __builtin_ctz(a | b);
a >>= __builtin_ctz(a);
do {
b >>= __builtin_ctz(b);
if (a > b)
swap(a, b);
b -= a;
} while (b);
return a << shift;
}
다만 이러한 최적화는 보통 필요하지 않으며, 대부분의 프로그래밍 언어는 이미 표준 라이브러리에 GCD 함수를 갖추고 있다는 점에 유의하십시오. 예를 들어 C++17에는 numeric 헤더에 std::gcd라는 함수가 있습니다.