최대공약수(GCD), 최소공배수(LCM) - 유클리드 호제법(Euclidean algorithm) - Python 예제

최대공약수 - Greatest Common Divisor

최대 공약수는 두 수를 모두 나눌 수 있는 수 중에 가장 큰 수이다.

ex) GCD of 15 and 7 is  1
ex) GCD of 25 and 15 is 5

---

최소공배수 - Least Common Multiple

최소 공배수는 두 수의 공통된 배수 중 가장 작은 수이다.

ex) LCM of 15 and 7 is 105
ex) LCM of 25 and 15 is 75

---

최대공약수(GCD)와 최소공배수(LCM)의 관계

최대 공약수와 최소 공배수는 아래의 관계를 가진다.

 

A * B / GCD of A and B = LCM of A and B

 

이를 위의 예시에 적용하여 풀면 아래와 같다

7 * 15 / 1 = 105 is LCM of 7 and 15
25 * 15 / 5 = 75 is LCM of 25 and 15

 

즉, 최대공약수를 알면 최소 공배수를 구하는 것은 굉장히 쉬운 일이다.

---

유클리드 호제법 - Euclidean Algorithm

최대공약수를 구하는 굉장히 보편적인 알고리즘이다.

 

유클리드 호제법을 사용하지 않고도 얼마든지 최대공약수를 구할 수 있지만 일반적으로 시간 복잡도는 O(N)을 가지게 된다.

for i in range(1, N):
        if A % i == 0 and B % i == 0:
            GCD = i

위와 같은 반복문을 통해서도 최대 공약수를 구할 수 있지만,

 

유클리드 호제법을 통해 최대공약수를 구하게 된다면 시간 복잡도를 O(logN)까지 줄일 수 있다.

 

호제법의 의미는 두 수가 서로 상대방의 수를 나누어서 원하는 수를 얻는 알고리즘을 의미한다.

 

유클리드 호제법은 아래의 절차를 따른다.

 

1. A, B는 자연수이다(A ≥ B).
2. A를 B로 나눈 나머지를 R이라고 한다.( R = A % B )
3. A와 B의 최대 공약수는 B와 R의 최대공약수와 같다. 따라서 B를 R로 나눈 나머지 R1를 구한다.
4. 나머지가 0이 될 때 까지 나누는 과정을 반복한다.
5. 나머지가 0이될 때의 나눈 숫자가 최대 공약수이다.(최종적으로 나뉘는 숫자와 나누는 숫자가 배수의 관계이기 때문)

결국, 위의 코드 대신 유클리드 호제법을 적용하기 위한 방법은 아래와 같다.

 

1. 두 값 중 큰 값을 찾는다. - A ≥ B
2. 아래의 과정을 R이 0이 될 때까지 반복한다.
   1. A % B = R
   2. A, B = B, R
3. R = 0 일때의 A가 최대공약수(GCD)이다.

위의 과정만 거치면 최대 공약수(GCD)가 도출된다.

 

최소 공배수(LCM)는 앞서 말한 관계를 적용하면, 단 한번의 연산으로 계산이 가능하다.

 

아래는 유클리드 호제법을 적용하여 최대 공약수와 최소 공배수를 구하는 파이썬(Python) 예제이다.

def GCDLCM(A, B):
    a, b = max(A, B), min(A, B)
    R = 1
    while R != 0:
        R = a % b
        a, b = b, R
    return [a, A*B//a] # 순서대로 최대공약수, 최소공배수이다.