[알고리즘] 최소 공배수(LCM, Least Common Multiple)

최소공배수(LCM, Least Common Multiple)를 구하는 여러 가지 방법이 존재하며, 이 중에서도 유클리드 호제법을 활용한 방법이 가장 효율적입니다. 아래에서는 여러 방법을 비교하고, 각 방법의 특징과 효율성을 설명하겠습니다.

 

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

이 방법은 두 수의 배수를 계산하고, 가장 작은 공통 배수를 찾는 매우 직관적인 방법입니다.

 

알고리즘

1. a와 b의 배수를 각각 계산합니다.
2. 두 수의 배수 중에서 가장 작은 공통 배수를 찾습니다.

def lcm_brute_force(a, b):
    max_ab = max(a, b)
    lcm_value = max_ab
    while lcm_value % a != 0 or lcm_value % b != 0:
        lcm_value += max_ab
    return lcm_value

# 예시
print(lcm_brute_force(24, 36))  # Output: 72

이 방법의 시간 복잡도는 O(a * b)로, 매우 비효율적입니다. 특히, 큰 수에 대해서는 실질적으로 사용하기 어렵습니다. 따라서, 이 방법은 이론적인 설명에 더 가깝습니다.

 

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

소인수분해를 통해 두 수의 최소공배수를 구할 수 있습니다. 이 방법은 두 수를 소인수분해한 후, 공통 소인수를 포함하여 모든 소인수의 최대 거듭제곱을 곱하는 방식입니다.

 

알고리즘

1. 두 수를 각각 소인수분해합니다.
2. 두 수에서 나타나는 모든 소인수의 최대 거듭제곱을 구합니다.
3. 그 소인수들의 곱이 두 수의 최소공배수입니다.

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 lcm_prime_factors(a, b):
    factors_a = Counter(prime_factors(a))
    factors_b = Counter(prime_factors(b))
    
    all_factors = factors_a | factors_b  # 모든 소인수의 최대 거듭제곱
    lcm_value = 1
    for factor in all_factors:
        lcm_value *= factor ** all_factors[factor]
    return lcm_value

# 예시
print(lcm_prime_factors(24, 36))  # Output: 72

이 방법은 소인수분해 과정이 필요하여 시간 복잡도 O(sqrt(n))을 가지며, 큰 수에 대해서는 효율적이지 않습니다. 특히, 유클리드 호제법 기반의 방법과 비교할 때 덜 효율적입니다.

 

3. 최대공약수(GCD) 기반 방법 (유클리드 호제법 이용)

유클리드 호제법을 사용하여 두 수의 최대공약수(GCD)를 구하고, 이를 활용하여 최소공배수를 계산하는 방법이 가장 효율적입니다.

 

알고리즘

1. 먼저 유클리드 호제법을 사용해 GCD를 구합니다.
2. 두 수의 곱을 GCD로 나누어 LCM을 계산합니다.

공식

그림 1

이유와 설명

최대공약수(GCD)와 최소공배수(LCM)는 밀접한 관계가 있습니다. 두 수의 곱은 그 두 수의 최대공약수와 최소공배수의 곱과 동일합니다. 즉, 아래와 같은 식이 성립합니다.

그림 2

그러므로 위의 그림 1의 공식은 그림 2를 이용해서 변형된 모습입니다. 이 공식을 사용하면 먼저 두 수의 최대공약수를 구한 다음, 이를 이용해 최소공배수를 빠르게 계산할 수 있습니다.

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

def lcm_gcd_based(a, b):
    return abs(a * b) // gcd(a, b)

# 예시
print(lcm_gcd_based(24, 36))  # Output: 72

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

 

결론

• 소인수분해 기반 방법: 이론적으로 정확하지만, 소인수분해 과정이 추가되어 큰 수에 대해서는 비효율적입니다.
• 완전 탐색 기반 방법: 매우 비효율적이며, 큰 수에서는 사용할 수 없습니다.
• GCD 기반 방법 (유클리드 호제법 이용): 가장 효율적이고 실용적인 방법으로, 특히 큰 수에 대해서도 빠르게 최소공배수를 구할 수 있습니다.