프로젝트 오일러 005

문제

5번 문제

1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

사이냅소프트

3으로 나누어 떨어지는 수는 3의 배수입니다. 2로도 3으로도 나누어 떨어지는 수는 2의 배수이면서 3의 배수입니다. 어떤 수가 1~10 사이의 모든 수로 나누어 떨어진다면, 그 수는 10개 수의 공배수입니다.

1과 20사이의 모든 수의 최소공배수를 찾는 문제입니다. 세 개 이상의 수의 최소공배수를 계산하는 방법은 먼저 두 수의 최소 공배수를 구한 다음, 그 수와 나머지 하나의 최소 공배수를 구하면 됩니다. 이것은 마치 1 + 2 + 3을 계산할 때, (1 + 2) + 3 과 같이 순서대로 계산하는 것과 같은 개념입니다. 또한 덧셈처럼 결합법칙과 교환법칙이 성립합니다.

이처럼 결합법칙과 교환법칙이 성립하는 연산을 특정한 연속열에 대해 반복하여 적용하는 경우 reduce (혹은 fold)를 적용하여 하나의 값으로 합칠 수 있습니다.

최소공배수

문제 풀이를 위해서는 먼저 두 수의 최소 공배수를 구하는 연산을 정의해야 합니다. 두 수의 최소 공배수는 두 수의 곱에 최대 공약수를 나눈 값입니다. 따라서 먼저 최대 공약수를 구해야 합니다.

최대공약수를 구하는 가장 쉽고 효율적인 방법으로는 유클리드의 호제법이 가장 잘 알려져 있습니다. 두 수를 서로 나누는 것을 반복하는 것인데요, 알고리듬 자체는 교과서에 나올 정도로 유명하기 때문에 다음과 같이 소개하겠습니다.

def gcd(a: int, b: int) -> int:
  if a < b:
    return gcd(b, a)
  b, r = divmod(a, b)
  if r == 0:
    return b
  return gcd(b, r)

큰 수를 작은 수로 나누어, 큰 수를 나머지로 만들고, 다시 작은 수를 그 나머지로 나누는 과정을 반복하면 종국에는 나누어 떨어지게 되는데, 그 때의 작은 수(나누는 수)가 최대 공약수가 됩니다.

그러면 최소 공배수는 다음과 같이 구할 수 있습니다.

def lcm(a: int, b: int) -> int:
  g = gcd(a, b)
  return (a // g) * b

이제 리듀스를 해보죠. reduce() 함수는 아주 옛날에는 파이썬의 내장함수였지만, 지금은 functools 라는 모듈에 살고 있습니다. 간단히 불러와서 사용하겠습니다. 결국 최소공배수 연산 함수와 reduce만 있으면 되는 문제였죠.

from functools import reduce

def gcd(a: int, b: int) -> int:
  if a < b:
    return gcd(b, a)
  b, r = divmod(a, b)
  if r == 0:
    return b
  return gcd(b, r)

def lcm(a: int, b: int) -> int:
  g = gcd(a, b)
  return (a // g) * b

print(reduce(lcm, range(1, 21)))