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

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

 

문제

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

 

입력

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

 

출력

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

 

---

1. 문제 접근 방식

처음에는 min, max로 정한 범위의 숫자로 x, y를 나누었을 때 떨어지는 수를 구하는 코드를 짰다.

## 시간초과
x, y = map(int, input().split())

for i in range(min(x, y), 0, -1):
    if x % i == 0 and y % i == 0:
        print(i)
        break

for j in range(max(x, y), (x*y+1)):
    if j % x == 0 and j % y == 0:  # j가 x와 y보다 큰 수이기 때문에 분자로 와야 함
        print(j)
        break

 

하지만 시간초과가 떴고... 찾아보았더니 유클리드 호제법(유클리드 알고리즘)을 사용해야 하였다.

 

🔍 유클리드 호제법이란?

2개의 자연수의 최대공약수를 구하는 알고리즘이다.

2개의 자연수 a, b에서 a를 b로 나눈 나머지를 r이라고 한다면, a와 b의 최대공약수와 b와 r의 최대공약수가 같다.

b를 r로 나눈 나머지가 0이 될 때까지 반복하며, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다.

 

24와 18의 최대공약수를 구해보면,

① 24를 18로 나눈 나머지 : 6

② 18을 6으로 나눈 나머지 : 0

→ 나머지가 0이 되었기 때문에 최대공약수는 6이 된다.

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

이렇게 최대공약수를 구했는데, 최소공배수도 구할 수 있다. 두 수 x, y는 다음과 같다.

x = a * 최대공약수

y = b * 최대공약수

 

이를 활용하여 최소공배수를 구할 수 있다. 최소공배수는 x와 y로 나누어 떨어지는 수 중에 가장 작은 수이다.

최소공배수 = x * y / 최대공약수

 

 

2. 풀이코드

## 유클리드 호제법

x, y = map(int, input().split())

# 최대공약수 구하기
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

# 최소공배수 구하기
def lcm(x, y):
    return (x * y) // gcd(x, y)

print(gcd(x, y))
print(lcm(x, y))

 

## 내장 함수 활용

import math

x, y = map(int, input().split())

print(math.gcd(x, y))
print(math.lcm(x, y))   # lcm() 함수는 파이썬 3.9 버전 이상부터 사용 가능함

파이썬 내장함수를 활용해서 구할 수 있다.

단, 최소공배수의 경우 파이썬 3.9 버전 이상부터 사용이 가능하다!

 

3. 참고 포스팅

백준 - 2609 (Python) - 최대공약수와 최소공배수

 

[백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python