최대공약수(GCD)를 구하는 방법

최대공약수(Greatest Common Divisor, GCD)는 두 개 이상의 수가 가질 수 있는 가장 큰 공통 인수를 의미합니다. GCD는 수학적 문제뿐만 아니라 컴퓨터 과학에서도 중요한 역할을 하며, 이와 관련된 다양한 알고리즘이 발전해 왔습니다. 이번 글에서는 가장 기본적인 방법부터 가장 효율적인 알고리즘까지 살펴보겠습니다.

 

1. 브루트 포스 방식

최대공약수를 구하는 가장 단순한 방법은 브루트 포스 방식입니다. 이 방법은 두 수의 공통 인수들을 모두 찾아내어 그 중 가장 큰 값을 찾는 방식입니다.

# Python으로 구현한 브루트 포스 방식

def gcd_brute_force(a, b):
    min_val = min(a, b)
    for i in range(min_val, 0, -1):
        if a % i == 0 and b % i == 0:
            return i

# 예시
print(gcd_brute_force(48, 18))  # 출력: 6

이 방식은 두 수의 최소값에서부터 하나씩 감소하면서 두 수의 공통으로 나누어지는 가장 큰 값을 찾습니다. 간단하지만, 두 수가 클 경우 반복 횟수가 매우 많아져 비효율적입니다.

 

2. 유클리드 호제법

유클리드 호제법은 GCD를 계산하는 데 있어서 훨씬 더 효율적인 방법으로 알려져 있습니다. 이 방법은 두 수를 나눈 나머지를 이용하여 반복적으로 계산합니다. 기본 아이디어는 두 수의 GCD가 작은 수와 그 나머지의 GCD와 같다는 점입니다.

# Python으로 구현한 유클리드 호제법

def gcd_euclidean(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 예시
print(gcd_euclidean(48, 18))  # 출력: 6

이 방법은 연산을 반복하면서 나머지가 0이 될 때까지 두 수를 갱신합니다. 유클리드 호제법의 시간 복잡도는 로, 브루트 포스 방식보다 훨씬 빠릅니다.

 

3. 스테인 알고리즘(이진 GCD)

나눗셈 연산보다 비트 연산이 더 효율적인 컴퓨터에서 쓸만한 스테인 알고리즘이 있습니다. 이 알고리즘은 나눗셈을 사용하지 않고 이진 연산을 사용하여 GCD를 계산합니다.

스테인 알고리즘은 다음과 같은 규칙을 따릅니다:

• 두 수가 모두 짝수일 경우, GCD는 두 수를 2로 나눈 값의 GCD에 2를 곱한 값입니다.
• 두 수 중 하나만 짝수일 경우, GCD는 짝수가 아닌 수와 동일한 수의 GCD입니다.
• 두 수가 모두 홀수일 경우, 두 수의 차를 이용하여 GCD를 계산합니다.

# Python으로 구현한 스테인 알고리즘

def gcd_stein(a, b):
    if a == b:
        return a
    if a == 0:
        return b
    if b == 0:
        return a

    if (a & 1) == 0:  # a가 짝수
        if (b & 1) == 0:
            return gcd_stein(a >> 1, b >> 1) << 1
        else:
            return gcd_stein(a >> 1, b)
    if (b & 1) == 0:  # b가 짝수
        return gcd_stein(a, b >> 1)

    # 둘 다 홀수일 때
    if a > b:
        return gcd_stein((a - b) >> 1, b)
    return gcd_stein((b - a) >> 1, a)

# 예시
print(gcd_stein(48, 18))  # 출력: 6

스테인 알고리즘은 특정 상황에서 유클리드 호제법보다 더 빠른 성능을 보입니다. 특히, 컴퓨터의 하드웨어에서 나눗셈 연산보다 비트 시프트가 더 빠른 경우 효율적입니다.

 

4. 알고리즘 비교

유클리드 호제법과 스테인 알고리즘 모두 상당히 효율적이지만, 상황에 따라 비트 연산이 가능한 스테인 알고리즘이 더 나은 성능을 발휘할 수 있습니다.

 

결론

최대공약수를 구하는 다양한 방법 중에서 브루트 포스 방식은 가장 단순하지만, 큰 수에 대해서는 비효율적입니다. 유클리드 호제법은 널리 사용되는 효율적인 방법이며, 스테인 알고리즘은 비트 연산을 이용하여 추가적인 최적화를 이룰 수 있는 방법입니다. 각 방법의 특성을 이해하고 상황에 맞는 알고리즘을 선택하는 것이 중요합니다.

다양한 상황에서 가장 적합한 알고리즘을 선택함으로써 연산 효율성을 극대화할 수 있습니다. 특히, 하드웨어와 소프트웨어의 특성에 따라 나눗셈과 비트 연산의 속도 차이가 클 경우 스테인 알고리즘을 선택하면 큰 차이를 만들어낼 수 있습니다.