[알고리즘] 최대 공약수(GCD, Greatest Common Divisor)

이번에는 최대공약수(GCD, Greatest Common Divisor)를 구하는 여러 알고리즘을 소개하겠습니다. 각 방법은 효율성이나 구현 방식에 차이가 있습니다.

 

1. 완전 탐색 방법 (Brute Force)

첫 번째는 완전 탐색 방법을 이용한 최대 공약수를 구하는 방법 입니다.

가장 직관적인 방법으로, 두 수의 공통된 약수 중에서 가장 큰 값을 찾는 방법입니다.

 

알고리즘

1. 두 수 중 작은 수를 선택합니다.
2. 그 수로부터 1까지 모든 수에 대해 두 수 모두를 나눌 수 있는지 확인합니다.
3. 두 수를 모두 나눌 수 있는 가장 큰 수가 최대공약수입니다.

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

# 예시
print(gcd_brute_force(24, 36))  # Output: 12

이 방법의 시간 복잡도는 O(min(a, b))입니다. 즉, 작은 수에 비례하여 시간이 걸리므로 큰 수의 경우 비효율적입니다.

 

2. 소인수분해 방법 (Prime Factorization)

두 수를 소인수분해하여 공통된 소인수의 곱으로 최대공약수를 구하는 방법입니다.

 

알고리즘

1. 두 수를 각각 소인수분해합니다.
2. 공통된 소인수의 최소 거듭제곱을 구합니다.
3. 그 소인수들의 곱이 최대공약수입니다.

from math import gcd
from collections import Counter

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def gcd_prime_factors(a, b):
    factors_a = Counter(prime_factors(a))
    factors_b = Counter(prime_factors(b))
    common_factors = factors_a & factors_b
    gcd_value = 1
    for factor in common_factors:
        gcd_value *= factor ** common_factors[factor]
    return gcd_value

# 예시
print(gcd_prime_factors(24, 36))  # Output: 12

소인수분해의 시간 복잡도는 O(sqrt(n))이지만, 이를 두 수에 대해 수행하고 공통된 소인수를 찾아야 하므로, 이 방법 역시 큰 수에 대해서는 비효율적입니다.

 

3. 유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법은 가장 효율적이고 널리 사용되는 최대공약수 구하는 방법입니다.

 

알고리즘

1. 두 수 a, b가 있을 때 a > b라고 가정합니다.
2. a를 b로 나눈 나머지 r을 구합니다.
3. GCD(a, b) = GCD(b, r)로 변환하며, 나머지가 0이 될 때까지 이 과정을 반복합니다.
4. 나머지가 0이 되었을 때의 b 값이 두 수의 최대공약수입니다.

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

# 예시
print(gcd_euclidean(24, 36))  # Output: 12

유클리드 호제법의 시간 복잡도는 O(log(min(a, b)))로, 매우 효율적입니다. 이 방법은 큰 수에 대해서도 빠르게 동작하며, 일반적으로 최대공약수를 구하는 가장 좋은 방법입니다.

 

결론

• 완전 탐색 방법: 매우 단순하지만, 큰 수에 대해 비효율적입니다.
• 소인수분해 방법: 이론적으로 정확하지만, 구현이 복잡하고 큰 수에 대해 비효율적입니다.
• 유클리드 호제법: 가장 효율적이고 널리 사용되는 방법으로, 대부분의 경우 최적의 선택입니다.