[Python | 2609] 최대공약수와 최소공배수

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

---

문제 설명

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

📌 시간 제한: 1초

---

입력

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

---

출력

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

---

문제 접근

처음에는 최대공약수(GCD)와 최소공배수(LCM)를 구하는 방법을 몰라서, 그냥 직관적으로 "공약수를 직접 찾으면 되지 않을까?"라고 생각하고 접근했다. 이 과정에서 1부터 작은 수까지 나누어보며 공약수를 찾는 방법을 사용했고, 최소공배수는 GCD를 활용하는 공식을 찾아 적용했다.

 

단순 구현 방식 (완전탐색)

처음 떠올린 방법은 1부터 두 수 중 작은 값까지 모든 수를 탐색하며 공약수를 찾는 것이다.

 

1. 최대공약수 (GCD) 구하기

• 1부터 min(a, b)까지 모든 수를 확인하며, 두 수를 동시에 나눌 수 있는 가장 큰 값을 찾는다.
• 시간복잡도: O(N) (최대 min(a, b)번 반복)

2. 최소공배수 (LCM) 구하기

$$ LCM(a, b) = \frac{a \times b}{GCD(a, b)} $$

• GCD를 구한 후 위 공식을 이용하여 LCM을 계산한다.

이 방식은 작은 수에서는 잘 동작하지만, 큰 수가 입력되면 비효율적이다. 예를 들어, a=1,000,000, b=999,999 같은 큰 수가 입력되면 최대 999,999번 반복해야 한다.  이런 문제 때문에, "더 효율적인 방법이 없을까?"를 고민하다 유클리드 호제법이라는 알고리즘을 알게 되었다.

 

유클리드 호제법

유클리드 호제법은 나머지를 이용하여 GCD를 빠르게 구하는 알고리즘이다. 두 수 a, b의 GCD를 구하는 과정은 다음과 같다.

$$ GCD(A, B) = GCD(B, A \mod B) $$

두 수 A, B가 있을 때, A를 B로 나눈 나머지를 R이라고 하면, \( GCD(A, B) = GCD(B, R) \) 이 성립한다. 즉, A를 B로 나눈 나머지를 새로운 B로 설정하며, 반복적으로 문제를 줄여나간다.

 

이 과정을 반복하다가 B가 0이 되면, 남아 있는 A가 GCD가 된다.

$$ GCD(A, 0) = A $$

즉, 나머지를 계속 구하는 과정을 반복하면, 결국 남는 값이 두 수의 GCD가 된다.

 

이 방법을 사용하면 연산 횟수를 크게 줄일 수 있고, 시간복잡도는 O(log N) 이다. 기존 완전탐색 방식(O(N))보다 훨씬 빠르게 GCD를 구할 수 있으며, 큰 수에서도 효율적으로 동작한다.

 

📌 시간 복잡도 분석

유클리드 호제법은 각 단계에서 나머지 연산(A % B)을 수행하면서, 문제 크기를 급격히 줄이기 때문에 O(log N)의 시간복잡도를 가진다.

1. 각 연산에서 A는 B로 줄어들고, B는 A % B로 갱신된다.
2. B의 값은 반복될수록 빠르게 감소하며, 최악의 경우(피보나치 수열 관계)에서도 감소 속도가 O(log N)에 수렴한다.
3. 이 과정을 반복하면 최대 log₂(N)번 안에 B가 0이 되어 GCD가 구해진다.

---

구현

코드 1 : 완전 탐색 (Brute Force)

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

# 최대공약수(GCD)
def gcd_div(a, b):
    min_num = min(a, b)  # 두 수 중 작은 값까지만 검사
    gcd = 1  # 최소 공약수는 1이므로 기본값 설정
    for i in range(1, min_num + 1):  # 1부터 min(a, b)까지 모든 수 검사
        if a % i == 0 and b % i == 0:  # 공약수인지 확인
            gcd = i  # 최대 공약수 갱신
    return gcd

# 최소공배수(LCM)
def lcm_div(a, b):
    gcd = gcd_div(a, b)  # 최대공약수 호출
    return (a * b) // gcd  # 최소공배수 공식 사용

print(gcd_div(a, b))
print(lcm_div(a, b))

 

 

코드 2 : 유클리드 호제법

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

# 유클리드 호제법을 이용한 GCD
def gcd_euclid(a, b):
    while b != 0:
        a, b = b, a % b  # a를 b로 갱신, b를 a % b로 갱신
    return a

# LCM 공식
def lcm_euclid(a, b):
    return (a * b) // gcd_euclid(a, b)

print(gcd_euclid(a, b))
print(lcm_euclid(a, b))