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

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

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

---

문제

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

입력

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

출력

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

예제 입력

24 18

예제 출력

6
72

풀이 1

import sys

# 표준 입력 대신 sys.stdin.readline()을 사용하여 입력 속도 향상
input = sys.stdin.readline

# 두 개의 정수를 입력받아 n1, n2에 할당
n1, n2 = map(int, input().split())

# 큰 값을 a에, 작은 값을 b에 할당
a = max(n1, n2)
b = min(n1, n2)

# b의 약수를 찾아서 lst 리스트에 추가
lst = []
for i in range(1, b + 1):
    if b % i == 0:
        lst.append(i)

# lst 리스트에서 a의 약수인 가장 큰 값을 찾아서 출력
for i in reversed(lst):
    if a % i == 0:
        print(i)
        break

# 두 수의 공배수를 구하는 과정
cnt1 = 1
cnt2 = 1
while True:
    if cnt1 * a == cnt2 * b: # 두 수의 공배수를 찾으면 출력하고 종료
        print(cnt1 * a)
        break
    elif cnt1 * a < cnt2 * b: # cnt1 * a가 작으면 cnt1 증가
        cnt1 += 1
    else: # cnt1 * a가 크면 cnt2 증가
        cnt2 += 1

 

이 코드의 시간 복잡도는 O(n log n)이다.

max() 함수와 min() 함수 호출은 O(1) 시간에 수행된다.
lst 리스트에는 b의 약수가 저장되므로, 리스트의 크기는 b의 약수의 개수(b의 약수의 총 개수는 O(약수의 개수))이다. 따라서 약수를 찾는 for 루프의 시간 복잡도는 O(약수의 개수)가 된다.
for i in reversed(lst): 루프의 시간 복잡도는 약수의 개수와 관련이 있다. 따라서 이 부분의 시간 복잡도는 O(약수의 개수)이다.
while 루프는 최악의 경우 cnt1 * cnt2번 반복된다. 이 루프 안에서 수행되는 비교 연산(cnt1 * a == cnt2 * b, cnt1 * a < cnt2 * b)은 O(1) 시간에 수행된다. 따라서 while 루프의 시간 복잡도는 O(cnt1 * cnt2)가 된다.
cnt1과 cnt2는 while 루프 안에서 각각 1씩 증가하므로, 최악의 경우 cnt1과 cnt2의 최댓값은 a와 b의 차이(|a-b|)이다. 따라서 while 루프의 시간 복잡도는 O(a * b)가 된다.
따라서, 이 코드의 전체적인 시간 복잡도는 O(n log n) + O(n) + O(n) = O(n log n)이다. (단, n은 max(n1, n2)와 min(n1, n2) 중 큰 값을 의미한다.)

이 코드는 두 수의 최대공약수와 최소공배수를 찾는 데에 있어서 비교적 간단하고 직관적으로 구현되어 있다. 그러나 큰 수에 대해서는 약수를 찾는 부분에서 시간 복잡도가 상당히 커지므로, 두 수가 매우 큰 경우에는 처리 속도가 느려질 수 있다. 이런 경우에는 보다 효율적인 알고리즘을 사용하는 것이 좋다.

풀이 2

유클리드 알고리즘을 사용하여 최대공약수를 구할 수 있다. 유클리드 알고리즘은 두 수의 최대공약수를 구하는 알고리즘으로, 큰 수를 작은 수로 나누어 나머지를 구하고, 나머지가 0이 아니면 작은 수를 나머지로, 나머지가 0이면 그 때의 작은 수가 두 수의 최대공약수이다.

최소공배수는 두 수의 곱을 최대공약수로 나눈 값이다.

아래는 유클리드 알고리즘을 사용하여 최대공약수와 최소공배수를 구하는 코드이다.

import sys
input = sys.stdin.readline

n1, n2 = map(int, input().split())

# 유클리드 알고리즘을 사용하여 최대공약수를 구함
a, b = n1, n2
while b != 0:
    a, b = b, a % b
gcd = a

# 최소공배수를 구함
lcm = n1 * n2 // gcd

print(gcd)
print(lcm)

위 코드의 시간 복잡도는 최대공약수를 구하는 부분에서 O(log(min(n1, n2)))이고, 최소공배수를 구하는 부분에서는 O(1)이다. 따라서 전체적인 시간 복잡도는 O(log(min(n1, n2)))이다. 유클리드 알고리즘은 두 수 중 작은 수의 대략적인 자릿수에 비례하는 횟수만큼의 연산을 수행하기 때문에, 큰 수에서도 빠른 시간에 최대공약수를 구할 수 있다.

참고자료

유클리드 호제법(Euclidean-algorithm)

파이썬의 reversed() 함수로 거꾸로 루프 돌리기 (vs. slicing 연산자 & reverse() 함수)