[수학] 유클리드 호제법(Euclidean Algorithm) 이론

Date: 2025.02.01 Updated: 2025.02.01

카테고리: Mathematics Theory

태그: algorithm Euclidean Algorithm mathematics number theory 알고리즘 유클리드 호제법 정수론 최대공약수 최소공배수 수학

💡 유클리드 호제법(Euclidean Algorithm) 개요

고대 그리스의 수학자 유클리드가 고안한 최대공약수(greatest common divisor, GCD) 계산 알고리즘.

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

\[\text{gcd}(a, b) = \text{gcd}(b, r)\]

이다.

$r=0$이라면, $a$, $b$의 최대공약수는 $b$가 된다.

🎯 목표

코딩 테스트에서 최대공약수와 관련된 문제가 나오면 빠르게 최대공약수를 찾기 위해 사용한다. 가장 간단하고 빠른 최대공약수 계산 알고리즘이다.
최대공약수를 활용하면 최소공배수(least common multiple, LCM)도 쉽게 구할 수 있다.
두 양의 정수뿐만 아니라 두 다항식의 최대공약수도 구할 수 있다.

🔑 알고리즘 동작 과정

두 양의 정수 $a$, $b$가 주어졌을 때 대소 비교를 한 뒤에 큰 수를 $a$로 두고 작은 수를 $b$로 둔다.
$a$를 $b$로 나눈 나머지가 $r$이라면 $a$에 $b$를 대입하고 $b$에 $r$을 대입한다.
$r=0$이 될 때까지 2번 과정을 반복한다.
$r=0$이 되면 $b$가 최대공약수가 된다.

🎨 예시

2484와 4212의 최대공약수를 구하는 과정은 다음과 같다.

\[a = bq + r \quad (a > b)\] \[4212 = 2484 \times 1 + 1728\] \[2484 = 1728 \times 1 + 756\] \[1728 = 756 \times 2 + 216\] \[756 = 216 \times 3 + 108\] \[216 = 108 \times 2 + 0\]

$108$이 최대공약수이다.

❓ 생각해보면 좋을 것들

최대공약수와 최소공배수의 관계

최대공약수와 최소공배수의 관계는 다음과 같다.

\[\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b\]

즉, 유클리드 호제법으로 최대공약수를 구한 다음, 두 양의 정수를 곱하고 최대공약수로 나누면 최소공배수를 구할 수 있다.

최초의 유클리드 호제법은 나누기 연산이 아닌 뺄셈 연산을 사용했다.

유킬리드의 원론(Elements)에서 소개한 방법은 아래와 같다.

두 수 $a$ 와 $b$ $(a > b)$가 있을 때, 큰 수에서 작은 수를 빼는 작업을 반복하여 두 수가 같아질 때까지 진행하면 그 값이 두 수의 최대공약수(GCD)가 된다.
예를 들어, 36과 15의 최대공약수를 찾는 과정을 보면:

\[36 - 15 = 21\] \[21 - 15 = 6\] \[15 - 6 = 9\] \[9 - 6 = 3\] \[6 - 3 = 3\] \[3 = 3\]

이 방법은 나누기 연산이 아닌 뺄셈 연산을 사용하여 최대공약수를 구하는 방법이다.

💻 언어별 코드 예시

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

int gcd(int a, int b) {
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

감자