[알고리즘] 최소공배수와 최대공약수

최소공배수와 최대공약수와 관련한 알고리즘 문제를 종종 접한다. 그때마다 중학교 수학을 찾아보며서 문제를 풀어나가곤 하는데 이번 기회에 이와 관련한 개념들을 정리하고자 한다.

• 최소공배수(Least Common Multiple, LCM)

  두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수를 의미한다.
  지름이 서로 다른 톱니바퀴가 서로 만나는 최초 시기, 운행 시간이 서로 다른 버스가 동시에 출발한 후 다시 만나는 최초 시기 등의 계산에 활용된다.

• 최대공약수(Greatest Common Divisor, GCD)

  두 수에 서로 공통으로 존재하는 약수 중 가장 큰 수를 의미한다. 가로와 세로 길이가 다른 벽에 남는 부분이 없도록 가능한 큰 타일을 붙이는 경우 타일의 한 변 계산 등에 활용된다.

• 최소공배수와 최대공약수의 관계

  두 수 x와 y의 최소공배수와 최대공약수는 아래와 같은 관계가 성립한다.

  $x\times y=LCM(x,y)\times GCD(x,y)$

  그 이유는 두 수를 각각 소인수분해했을 때 최소공배수는 두 수의 인자를 모두 포함하고있고 최대공약수는 두 수의 공통된 인자만 포함하고있기 때문이다.

  4와 10을 예를 들어보자.
  4를 소인수분해하면 $2^2$, 10을 소인수분해하면 $2*5$이다.
  두 수의 최소공배수는 모든 인자를 포함한 $2^2*5=20$ 이며
  두 수의 최대공약수는 공통된 인자인 2이다.

  두 수의 곱과 최소공배수와 최대공약수의 곱은 40으로 일치한다.

  이제 위 등식에서 아래와 같은 식을 도출할 수 있다.

  $LCM(x,y)=x\times y\div GCD(x,y)$
  $GCD(x,y)=x\times y\div LCM(x,y)$

  즉, 최소공배수와 최대공약수 중 하나만 구해도 두 수의 곱에서 결과를 나누어 나머지 하나를 구할 수 있는 것이다.

• 유클리드 호제법

  그렇다면 최소공배수를 구하는 것이 쉬울까 최대공약수를 구하는 것이 쉬울까? 유클리드 호제법을 이용하면 최대공약수를 아주 간편하게 구할 수 있다.

  기원전 300년경에 이 내용을 밝힌 유클리드의 명석함을 2300년이 더 지나서야 깨닫게 된다.

  2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
  이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

  위 내용을 파이썬 코드로 구현하면 다음과 같다.

  while b:
          rest = a % b
          a = b
          b = rest

  a에서 b를 나누고 a를 b로, b를 나머지로 대체해가면서 b가 0이 되기 전까지(정수는 0이 되어야 False이므로) 작업을 무한히 반복한다.

  b가 0이 될 때 작업을 중단하고 그 시점의 a가 최대공약수가 된다.

  나머지 절차는 매우 간단하다. 두 수의 곱에 방금 구한 최대공약수를 나누면 최소공배수가 나오게 된다.