[Coding Test][Python] 백준 2609번: 최대공약수와 최소공배수

문제

https://www.acmicpc.net/problem/2609

 

 

최대 공약수: 두 자연수의 공통된 약수 중 가장 큰 수

최소 공배수: 두 자연수의 공통된 배수 중 가장 작은 수

재귀함수

n, m = map(int,input().split())

# 최대 공약수
def gcd(a, b):
    if (b == 0): return a
    else: return gcd(b, a%b)

print(gcd(n,m))

# 최소 공배수
print(n*m//gcd(n,m))

 

유클리드 호제법(Euclidean Algorithm)을 활용하면 쉽게 최대 공약수를 도출해낼 수 있다.

최소 공배수는 두 자연수의 곱을 최대 공약수로 나누면 구할 수 있다.

 

유클리드 호제법(Euclidean Algorithm)
큰 수를 작은 수로 나눈 나머지 r을 구하고, 작은 수와 그 나머지 r로 다시 나머지를 구하는 과정을 반복하여
나머지가 0이 될 때까지 진행하며, 이때 마지막 나누는 수가 최대공약수가 된다.

 

반복문

n, m = map(int,input().split())

# 반복문
t1, t2 = n, m
while(t2 > 0):
    t1, t2 = t2, t1%t2

print(t1)
print(n*m // t1)

 

두 방식 모두 O(log N)으로 시간복잡도 측면에서는 차이가 없다. 

(실행 환경과 메모리 사용량에서 차이가 발생할 수 있겠다)