Daily Algorithm - Day 4

Q. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

정수 1~20으로 나누었을 때 나머지가 나오지 않는 제일 작은 수(= 최소공배수)를 구하는 문제다.

파이썬의 경우 math 모듈을 지원하기 때문에 코드 1줄이면 답을 구할 수 있다.

• math 모듈을 사용하는 경우

//Python
import math

print(math.lcm(*range(1,21)))

>>> 232792560

너무 간단한거 같으니 검산용 코드를 추가해주고 중복사용할 변수도 지정해주자.

import math

numbers = range(1,21)
LCM = math.lcm(*numbers)

# 만약 numbers 안의 숫자로 나누어지지 않는다면 그 숫자를 출력해준다.
for i in numbers :
    if LCM % i == 0 :
        pass
    else :
        print(f"{LCM} can't be divided by {i}")

print(LCM)

>>> 232792560

가시성도 좋고, 계산도 빠르다. 실무에서는 무조건 이 코드를 사용하게 될 것이다.

• math 모듈을 사용하지 않는 경우

그래도 출제의도에 맞춰서 모듈 없이도 코드를 작성해보자.
우선 수학적으로 두 정수 a, b가 있을 때 a*b 를 최대공약수로 나누면 최소공배수가 나온다.
즉, 최대공약수를 구하면 최소공배수도 구할 수 있다.
최대공약수를 빠르게 구할 수 있는 유클리드 알고리즘이 있으니 이를 활용하자.

# 유클리드 알고리즘을 이용한 두 숫자의 최소공배수를 구하는 함수
def LCM(a, b): 
    x, y = a, b
    while y > 0:
        x, y = y, x % y
    GCD = x
    return a * b // GCD 

이 함수로는 2 숫자의 최소공배수를 구할 수 있으니, 앞에서부터 수 2개씩 접근하면서 이들을 모두 포괄할 수 있도록 최소공배수를 갱신해 나간다면 답을 구할 수 있을 것이다.

# 배열에서 순차적으로 최소공배수를 구한다. = 배열 속 숫자 전부의 최소공배수를 구한다.
def LCM_multi(arr):
    x = arr[0]
    for i in arr:
        x = LCM(x, i)
    return x

최종적으로 나온 코드는 다음과 같다.

numbers = range(1,21)

def LCM(a, b): 
    x, y = a, b
    while y > 0:
        x, y = y, x % y
    GCD = x
    return a * b // GCD 

def LCM_multi(arr):
    x = arr[0]
    for i in arr:
        x = LCM(x, i)
    return x
    
print(LCM_multi(numbers))

>>> 232792560

오늘은 여기까지.

-2024.12.24-