[Python] 백준 2609번 최대공약수와 최소 공배수 (유클리드 호제법)

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

예제 입력	예제 출력
24 18	6 72

 

정답

import sys

result_gcd, result_lcm = 0, 0


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


def lcm(a, b):
    return a * b // result_gcd


if __name__ == '__main__':
    num1, num2 = map(int, sys.stdin.readline().strip().split())

    result_gcd = gcd(num1, num2)
    result_lcm = lcm(num1, num2)

    print(result_gcd, result_lcm)

 

Tip

유클리드 호제법이란?

두 수의 최대 공약수를 구하는 알고리즘이다.

2부터 나누어 최대 공약수를 구하는 알고리즘을 짜게 된다면 a, b 중 작은 수까지 나누어 봐야하기 때문에 시간 복잡도는 O(N)이 되게 된다. 하지만 유클리드 호제법을 이용하게 되면 시간 복잡도는 O(logN)까지 줄어들게 된다!

 

유클리드 호제법의 공식은 r을 a와 b를 나눈 나머지라고 가정하고 보면 gcd(a, b) = gcd(b, r)이고 "r이 0이면 그 때 b가 최대 공약수"라는 알고리즘을 갖고 있다.

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

이 코드가 그러한 의미를 갖고 있다.

쉽게 알아보기 위해서 표로 한 번 봐보자.

 

SEQ	func	a	b	r
1	gcd(24, 18)	24	18	6
2	gcd(18, 6)	18	6	0
3	gcd(6, 0)	6	0	X

※ 24,18를 넣었다고 가정한다.

 

SEQ	func	a	b	r
1	gcd(18, 24)	18	24	18
2	gcd(24, 18)	24	18	6
3	gcd(18, 6)	18	6	0
4	gcd(6, 0)	6	0	X

※ 18,24를 넣었다고 가정한다.

 

최소 공배수

최소 공배수를 구하는 식은 a * b / a와 b의 최대공약수라고 보면 된다.

def lcm(a, b):
    return a * b // result_gcd

만약 result_gcd를 전역변수로 가지고 있다 쓰지 않고 gcd를 불러 재귀함수를 다시 호출하면 중복된 재귀함수를 호출하는 것이므로, 나는 전역변수로 빼서 바로 사용했다. 백준 기준으로 시간 또한 4ms가 빨라졌다.