2609 최대공약수, 최소공배수

2609 최대 공약수, 최소공배수

본 정리는 알고리즘 공부 정리를 목적으로 작성했습니다.

1. 유클리드 호제법 증명 및 이해

"gcd(최대공약수)를 이해하는데 있어 유클리드 호제법을 사용한다"라는 말과 함께 넘어간 적만 2번 이상이다. 문제를 보고 3초안에 유클리드 호제법을 기억해내지 못한 내 아쉬운 기억력을 배려해 유클리드 호제법을 증명하는 걸 정리할 예정이다.

• 유클리드 호제법 : A,B의 최대공약수는 B와 R의 최대공약수와 같다.
  $A = BC + R$
  라는 식은 B에 G만큼 곱하고 R을 더하면 A라는 식이다.
  이때 A와 B의 최대공약수를 G라고 가정해보겠다. (N, M은 서로소)
  $A = G*N, B = G*M, G*N = G*M*q + R$
  $R = G*(N-M*q) ,B = G*M$
  이때 N-Mq 와 M이 서로소라면 R와 B의 최대공약수 또한 G가 된다.
  귀류법을 활용한다면 N-Mq와 M이 서로소인것이 확인되기에 유클리드 호제법은 참이라는 것을 도출할 수 있었다.
• 최대공약수 함수

def gcd(a,b):
    while a > 0:
        r = a%b 
        if r == 0:
            return b 
        else:
            a = b 
            b = r 

이렇듯, 만약 나머지인 r이 0 이 되는 순간, a와 b 중 b가 최대공약수가 되기에 b를 반환해준다.

• 최소공배수 함수

def lcm(a,b): # 최소공배수는 두 수의 곱을 최대공약수로 나눈 것과 같다.
    return int((a*b)/ gcd(a,b))

두 숫자 a,b를 곱해주면 최대공약수가 2번 곱해지고, 나머지 요소들은 최소공배수를 구하는 과정에서 빠지면 안되는 요소들임이 분명하다. 즉, a와 b를 최대공약수를 1번만 넣어주면 최소공배수를 만들 수 있다고 판단할 수 있다. 따라서 두 수의 곱을 최대공약수로 한번 나눈 값이 최소공배수다.

유클리드 호제법 관련된 참고한 자료

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=papers&logNo=140207307545