[백준] 2609번 최대공약수와 최소공배수 - Python / 알고리즘 기초 1/2 - 수학 1

---

---

---

💡 문제

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

입력

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

출력

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

---

💭 접근

이 문제는 Python에서 기본적으로 제공하는 math module의 gcd(), lcm() 함수를 사용하여 풀 수도 있고, 유클리드 호제법이란 알고리즘을 사용하여 해결할 수도 있다.

유클리드 호제법?
숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대공약수가 같다는 것을 의미한다.

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

이러한 개념을 활용하여 b가 0이 될때까지 반복하면 최대공약수를 구할 수 있고, 최소공배수는 a, b의 곱을 a, b의 최대 공약수로 나누면 나오게 된다.

gcd(a, b) x lcm(a, b) = a x b

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

---

📒 코드

# Python module을 사용한 풀이
from math import gcd, lcm

a, b = map(int, input().split())
print(gcd(a, b))
print(lcm(a, b))

# 유클리드 호제법을 사용한 풀이
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

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

a, b = map(int, input().split())
print(gcd(a, b))
print(lcm(a, b))

---

💭 후기

유클리드 호제법처럼 이러한 수학적 성질을 활용하여 문제를 해결할 수 있는 전반적인 시야를 넓혀야겠다.

---

🔗 문제 출처

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

---