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

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

Python) 백준 2609번 - 최대공약수와 최소공배수 문제 풀이

오늘은 백준 2609번 문제인 최대공약수와 최소공배수를 Python으로 풀어보겠습니다. 이 문제는 두 개의 자연수가 주어졌을 때, 최대공약수(GCD)와 최소공배수(LCM)를 구하는 문제입니다.

---

문제 설명

주어진 두 자연수의 최대공약수와 최소공배수를 출력하는 프로그램을 작성하세요.

입력

• 첫 번째 줄에 두 개의 자연수가 주어집니다. (1 ≤ 두 수 ≤ 10,000)

출력

• 첫째 줄에 주어진 두 수의 최대공약수(GCD)를 출력하고,
• 둘째 줄에 최소공배수(LCM)를 출력합니다.

---

문제 해결 과정

최대공약수(GCD)와 최소공배수(LCM)는 수학에서 자주 사용되는 개념입니다. 이번 문제에서는 Python을 활용해 두 수의 최대공약수와 최소공배수를 구하는 방법을 정리합니다.

🔍 핵심 개념

1. 최대공약수(GCD): 두 수의 공통된 약수 중 가장 큰 값입니다.
2. 최소공배수(LCM): 두 수의 공통된 배수 중 가장 작은 값으로, 두 수의 곱을 최대공약수로 나눈 값과 동일합니다.

💡 풀이 전략

• 최대공약수(GCD)를 구하는 방법 중 하나로는 유클리드 호제법이 있습니다. 이는 반복적인 나눗셈을 통해 쉽게 구할 수 있습니다.
• 최소공배수(LCM)는 두 수의 곱을 최대공약수(GCD)로 나눈 값으로 구할 수 있습니다.

---

🔨 코드 구현

# 최대공약수를 구하는 함수 (유클리드 호제법 사용)
def GCD(a, b):
    while b:  # b가 0이 될 때까지 반복
        a, b = b, a % b
    return a  # 최대공약수 반환

# 최소공배수를 구하는 함수
def LCM(a, b):
    return (a * b) // GCD(a, b)  # 두 수의 곱을 최대공약수로 나눠 최소공배수 계산

# 입력받은 두 수를 리스트로 변환
numbers = list(map(int, input().split()))  # 두 정수를 입력받아 리스트로 저장

# 최대공약수 계산
gcd = GCD(numbers[0], numbers[1])
print(gcd)  # 최대공약수 출력

# 최소공배수 계산
lcm = LCM(numbers[0], numbers[1])
print(lcm)  # 최소공배수 출력

---

🚀 코드 설명

1. GCD 함수는 유클리드 호제법을 사용하여 두 수의 최대공약수를 계산합니다. 두 수를 계속 나머지 연산을 통해 나누어 나가며, 나누어떨어질 때까지 반복합니다.
2. LCM 함수는 두 수의 곱을 최대공약수로 나누어 최소공배수를 구합니다. 최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같기 때문에 효율적으로 계산할 수 있습니다.
3. 입력받은 두 자연수를 list(map(int, input().split()))을 통해 리스트로 변환하여 각각의 값을 저장합니다.
4. 최대공약수와 최소공배수를 계산하여 각각 출력합니다.

---

🧐 배운 점

이번 문제를 통해 유클리드 호제법을 이용한 최대공약수(GCD) 구하는 방법과, 이를 바탕으로 최소공배수(LCM)를 구하는 방법을 복습할 수 있었습니다. 특히, 유클리드 호제법은 매우 빠르고 효율적으로 최대공약수를 구할 수 있는 방법이기 때문에, 많은 문제에서 유용하게 사용할 수 있습니다.

---

🔚 마무리

최대공약수와 최소공배수를 구하는 문제는 수학적인 기초 개념이 잘 정리되어 있어야 쉽게 풀 수 있습니다. 이번 풀이에서는 기본적인 수학 개념을 Python 코드로 구현해 보았으며, 유클리드 호제법을 활용해 효율적으로 문제를 해결할 수 있었습니다. 앞으로 더 복잡한 문제에서도 이 개념을 확장하여 적용할 수 있기를 기대합니다.