[백준] 2609번 최대공약수와 최소공배수 (파이썬)

 

문제

 

2609번: 최대공약수와 최소공배수

 

 

 

정답 소스코드 (Python)

 

def gcd(x,y):
    while(y):
        x,y=y,x%y
    return x

num1,num2=map(int,input().split())
result=gcd(num1,num2)
print(result)
print(int(num1*num2/result))

 

 

풀이  (Python)

 

 

이 문제는 최대공약수를 구하는 방법을 모른다면 힘든 문제이다. 두 수의 각자 약수를 구한 후 비교하여 최대공약수를 구하게 되면, 시간초과가 발생한다.

알고리즘 공부를 하게 되면 처음으로 수학 파트를 공부하게 되는데 이때 꼭 알아야 하는 유형 중 하나인 것은 유클리드 호제법을 활용하여 최대공약수 관련문제를 풀이하는 것이다. 

 

 

Point 1)  유클리드 호제법 활용

유클리드 호제법은 최대공약수(=GCD)를 매우 효율적으로 구할 수 있는 방법을 제시한다.

 

 

유클리드 호제법

 

 

유클리드 호제법에서 (a,b)의 공약수를 구할  때 예시는  a=18, b=12인 경우 18과 12의 최대 공약수는 12와 6의 최대 공약수와 동일하다는 것을 알려준다. 이후 12를 6으로 나눈 나머지가 0이므로 6이 18과 12의 최대 공약수가 되게 된다.

즉 (a, b)=(b,a%b) 를 반복적으로 시행하여 나머지가 0이 나오는 경우 b자리 해당 자연수가 최대 공약수라는 뜻이다.

 

 

위의 유클리드 호제법을 파이썬 코드로 작성하면 아래와 같다.

def gcd(x,y):
    while(y):
        x,y=y,x%y
    return x

 

 

리턴값은 최대공약수이고 두 수의 곱에서 최대공약수를 나누면 최소공배수이기 때문에 

print(int(num1*num2/result))

 

이처럼 문제풀이를 해나갈 수 있다.