[알고리즘/파이썬] 유클리드 호제법 - 최대공배수(GCD), 최소공배수(LCM)를 구해보자

유클리드 호제법이란?

두 자연수의 최대공약수를 구하는 알고리즘으로 유클리드라는 사람에 의해 발견되어 그 이름을 땄다.

호제법은 서로 나누는 방법이라는 뜻으로 두 수가 서로 나누며 원하는 값을 얻는 방법을 말한다.

두 자연수의 최대공약수를 구함으로써 자연스럽게 최소공배수도 구할 수 있다.

 

참고로,

최대공약수 GCD는 Greatest Common Divisor의 약자이고

최소공배수 LCM은 Least Common Multiple의 약자이다.

 

사전적 정의

 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
(출처: 위키백과)

---

기존 방식의 문제점

유클리드 호제법 이전의 기존 방식의 문제점은 크게 두 가지가 있었다.

 

1. 수가 크면 계산이 복잡해 진다.

2304와 1440의 최대공약수를 구한다고 가정해보자.

기존 방식대로하면

2304와 1440을 각각 2로 나누고, 또 2로 나누고.. 2로 못나누면 3으로 나누고...

더 이상 공통으로 나눌 수 없을 때까지 나눈후에 그 공통부분을 최대공약수로 구할 수 있었을 것이다.

이런식으로 일일히 다 나눈후에 공통적으로 곱해져있는 부분이 최대공약수가 되는 것이다.

이는 숫자가 클수록 구하기가 어려워진다는 단점이 있다.

 

2. 공통의 약수를 찾기가 어려운 경우

만약 403과 155를 위의 방식대로 계산하려면 무엇으로 나눠야 할까?

라고 생각하면 한참이 걸릴 수가 있다.

이렇게 공통의 약수를 바로 찾기가 어려운 경우가 있을 수 있을 것이다.

 

유클리드 호제법 사용하기

유클리드 호제법은 다음과 같은 방식으로 진행된다.

1. 큰 수를 작은 수로 나눈다.

2. 나눈 수를 나머지로 계속 나눈다.

3. 나머지가 0이 나오면 그때 나누는 수가 최대공약수

 

위에서 계산한 2304와 1440의 최대공약수를 구해보자

2304 / 1440(나눈 수) = 1 * 1440 + 864(나머지)

1440 / 864 = 1 * 864 + 576

864 / 576 = 1 * 576 + 288

576 / 288 = 2 * 288 + 0

나머지가 0이 나왔기 때문에 그때 나눈 수인 288이 최대 공약수인 것이다.

 

이를 그림으로 표현해보면,

위 눈금의 한칸이 288이라고 가정하면,

2304는 8칸짜리, 1440은 5칸짜리가 되는 것이다.

이러한 상태에서 계속해서 남은 칸끼리만 빼주게되면

결국 더 이상 나눌 수 없는 한칸만 남게되고, 그것이 최대공약수인 것이다.

결국 모든 수들은 모두 최대공약수의 집합체라고 할 수 있는데, 그 점을 잘 이용한 계산법인 것 같다.

 

파이썬 코드로 풀어보기

기존의 방식대로 문제를 풀게되면

두 수가 a, b(a>b)라고 가정했을 때, 2부터 b까지 나눠질 때까지 나눈후에,

다시 그 두 수를 나눠서  2부터 작은수까지 전부 나눠봐야 하기 때문에 최악의 경우 O(n)의 시간복잡도를 가진다.

하지만 유클리드 호제법을 이용하면 O(logN)으로 시간복잡도를 줄일 수 있다.

 

gcd = 0

def euclid(a,b):
    global gcd
    if a % b == 0:
        gcd = b
        return;
    # 나머지 연산 이용하여 재귀
    euclid(b,a % b)

if __name__ == "__main__":
    euclid(2304, 1440)
    print(gcd) # 288
    # 최소공배수는 최대공약수에 각 수를 최소공배수로 나눈것을 곱해준다.
    lcm = gcd * (2304 // gcd) * (1440 // gcd) 
    print(lcm) # 11520