최소 공배수

https://www.acmicpc.net/problem/1934
문제를 보면 입력 값 두 수의 최소의 공통적인 배수를 구하면 되는 문제이다.
두 수(a, b)가 같은 수가 될때까지 더 작은 수에 배수를 늘리면서 같은수가 나올때까지 반복문을 실행하면 될것 같아서 그렇게 코드를 작성하였다.

실패

import sys

n = int(input())
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())

    i = 1  # a 값의 배수
    j = 1  # b 값의 배수
    while a * i != b * j:  # a와 b가 같은 배수가 될때까지 반복문 실행.
        if a * i > b * j:
            j += 1  # a가 크면 b의 배수를 늘림
        else:
            i += 1  # b가 크면 a의 배수를 늘림
    print(a*i)

결과는 시간초과가 나오게 되었다. 코드상 하나씩 비교하면서 1배수씩 올리니 시간이 오래 걸리는가 보다.
최소 공배수에 대해 공부하다 보니 최소 공배수를 구할려면 최대 공약수를 알아야 된는 것을 알게 되었다.

최대 공약수

최대 공약수를 구하는 식으로 '유클리드 호제법' 이라는 방법이 있다. 중학생때 배우는 수학이라고 하는데 기억이 전혀 나지 않는다.

유클리드 호제법

두 양의 정수 a, b가 있다고 가정(a > b)하면 a에서 b를 나눈 나머지가 r이라고 가정할 때 a % b = b % r 이라고 한다. 이 때 r = 0 이면 두 수 a, b 중 b 값이 최대 공약수가 된다.

최소 공배수

두 양의 정수 a, b의 곱에 두 양의 정수의 최대공약수를 나누어주면 최소 공배수가 된다.
a * b // 최대 공약수

즉 최소 공배수를 Python 코드로 표현을 하면

a = 6
b = 10
# 최대 공약수
def nums(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a
    
 # 최소 공배수
 a * b // nums(a, b)

이런 식으로 표현할 수 있다.

정답

import sys

n = int(input())
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    
    # 최대 공약수를 구하는 함수 생성
    def nums(a, b):
        while b != 0:
            r = a % b
            a = b
            b = r
        return a

    print(a * b // nums(a, b))  # 최소 공배수

정답을 풀고 조금더 찾아보니 Python에서는 math 라이브러리에 최소 공배수와 최대 공약수를 구하는 함수가 있다는 것을 알게되었다.

import math

math.gcd(a, b)  # 최대 공약수
math.lcm(a, b)  # 최소 공배수

위와 같이 함수를 사용하면 바로 구할수가 있다.

마치며

오늘 알고리즘 문제를 풀면서 최대 공약수와 최소 공배수에 대해서 공부를 하게 되었다. 결과적으로는 잊었던 수학적인 개념을 정리하게 된 시간이었기도 하지만 Python 라이브러리에 대해 더 알고 있었으면 그냥 바로 해결되는 문제였다. 알고리즘문제를 계속 풀면서 Python 라이브러리에 대해서도 공부를 해야겠다.