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

 

 

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

문제 바로 가기

---

📌 문제

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

 

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

 

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

 

 

 

📝 문제 접근 방법

핵심 아이디어

1. 최대공약수(GCD, Greatest Common Divisor)

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

 

2. 최소공배수(LCM, Least Common Multiple)

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

 

3. 유클리드 호제법 (Euclidean Algorithm)

두 수의 최대공약수를 구하는 효율적인 알고리즘으로
큰 수와 작은 수의 나머지 연산을 반복적으로 수행하여 최대공약수를 구함

 

기본 관계

GCD(a, b) = GCD(b, a % b)

• 여기서 a % b 는 a 를 b 로 나눈 나머지입니다.
• 나머지가 0이 될 때, 마지막 남은 b 가 두 수의 최대공약수가 됩니다.

 

원리: 두 수 a 와 b 의 공약수는 b와 a % b 의 공약수와 동일합니다.

• 어떤 수 x 가 a 와 b의 공약수라면
  • x | a (x 는 a 를 나눌 수 있음)
  • x | b (x 는 b 를 나눌 수 있음)
  • 따라서 x | r (x 는 r도 나눌 수 있음)
• 결과적으로 x는 a, b, a % b 의 공약수입니다.

 

작동 과정

1. 큰 수 a를 작은 수 b로 나눠 나머지 r를 구합니다
2. a를 b로, b를 r로 교체하여 나머지가 0이 될 때까지 반복합니다.
3. 나머지가 0이 되는 순간, 마지막 남은 b가 최대공약수입니다.

 

최소공배수와 최대공약수의 관계

LCM(a, b) = (a * b) // GCD(a, b)

• 두 수의 곱은 최대공약수와 최소공배수의 곱과 같습니다.

 

 

 

👩‍💻 나의 답안

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

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

a, b = tuple(map(int, input().split()))

print(gcd(a, b))
print(lcm(a, b))

 

 

 

🔍 다른 사람 답안

import math

a, b = map(int, input().split())

gcd = math.gcd(a, b)
lcm = (a * b) // gcd

print(gcd)
print(lcm)

 

 

 

✨ 새로 알게 된 점

1. 유클리드 호제법

최대공약수를 구하는 데 유클리드 호제법이 얼마나 효율적이고 간단한 알고리즘인지 다시 한번 확인할 수 있었습니다. 큰 수와 작은 수의 나머지 연산을 반복하여 계산하므로, 시간 복잡도가 $O(\log N)$로 매우 빠르다는 점이 유용했습니다.

 

2. Python 내장 함수 활용

Python에서는 math.gcd()를 제공하여 유클리드 호제법을 직접 구현하지 않고도 최대공약수를 구할 수 있다는 점이 편리했습니다. 최소공배수는 LCM = (a * b) // GCD를 통해 추가 연산으로 간단히 구할 수 있어, 코드가 더 간결해졌습니다.