코딩테스트 문제 (26) - 최대 공약수, 최소 공배수

이번 포스트에서는 최소공약수, 최대공배수를 구하는 방법을 알아보겠습니다.

최대 공약수

최대 공약수는 2개의 자연수를 각각 나누어서 나머지가 0이 되는 최대 자연수를 말합니다. 간단하게 2개의 자연수를 받아 2부터 작은 자연수까지 모두 나누어보면 구할 수 있지만 $O(N)$의 시간 복잡도가 소요됩니다. 유클리드 호제법을 사용하면 $O(\log N)$ 에 최대 공약수를 구할 수 있습니다.

유클리드 호제법

유클리드 호제법은 인류사에서 가장 오래된 알고리즘 중 하나로 알려져 있는 알고리즘입니다.

2개의 자연수 a, b (a > b) 에 대해서 a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같습니다. (GCD(a,b) = GCD(b, a%b))

• a, b의 최대공약수를 g라고 하면 a=gA, b=gB 로 표현할 수 있고, p를 a//b 라 했을때 a=bp+r 은 gA=gBp+r 이 되고 r=g(A-Bp) 가 됩니다. 여기서 보이고 싶은 것은 b=gB 와 r=g(A-Bp) 의 최대공약수가 g임을 보이고 싶은 것이므로 귀류법을 사용해 b와 r의 최대공약수가 g가 아니라고 가정합니다.
• b와 r의 최대공약수가 g가 아니라면 B와 A-Bp 간에 공통으로 나누어지는 정수가 존재한다는 뜻인데 그렇다면 A와 B가 어떤 정수에 대해 공통으로 나눠지게 됩니다. 하지만 a, b의 최대공약수가 g이므로 A, B는 서로소가 되므로 모순입니다. 따라서 b와 r의 최대공약수가 g가 됩니다.

b와 r의 최대 공약수를 구하기 위해서는 b를 r로 나눈 나머지를 r' 이라 했을 때, r과 r'의 최대 공약수를 구합니다. (GCD(a,b) = GCD(b, r) = GCD(r, r')) 이를 나머지가 0이 될 때까지 재귀적으로 반복합니다. 최대 공약수는 나머지가 0이 될 때의 나누는 수가 됩니다. 

이를 다음과 같이 간단히 구현할 수 있습니다.

def gcd(a,b):
    assert a > b
    return gcd(b, a % b) if not a % b else 0

 

최소 공배수

최소 공배수는 두 자연수의 공통된 배수 중 가장 큰 값입니다. 우리가 위의 방법으로 최대 공약수를 구했다면 최소 공배수는 LCM(a, b) = GCD(a, b) * (a / GCD(a, b)) * (b / GCD(a, b)) 로 구할 수 있습니다. 이를 구현하면 다음과 같습니다.

def lcm(a,b):
    def gcd(a,b):
        assert a > b
        return gcd(b, a % b) if not a % b else a % b
        
    gcd_ = gcd(a,b)
    
    return gcd_ * (a // gcd_) * (b // gcd_)

 

참조

• myjamong.tistory.com/138