CodeDrive

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

일단 최소공배수를 구하기 위해서 최대공약수(gcd)를 구하는 함수도 필요하다. 왜냐하면 최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같기 때문이다. N개의 최소공배수를 구하는 것도 크게 다르지 않다. N개가 있다면 그 중 계속 2개를 골라서 최소공배수를 구하고 그 값을 다시 arr 배열에 담는다. 이 과정을 arr의 원소가 1개가 남을 때까지 하면 그 남은 원소가 N개의 수들의 최소공배수가 되는 것이다.

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3,12의 최대공약수는 3, 최소공배수는 12이므로 solution(3,12)는 [3,12]를 반환해야 합니다.

 최대공약수를 구하는 방법중 가장 좋은 방법은 유클리드 호제법을 사용하는 것이다. 작은 수의 경우에는 상관 없으나 문제와 같이 수가 커질 경우에는 유클리드 호제법이 효율적이기 때문이다. 

 유클리드 호제법이란 '정수 a,b,q,r(b!=0)에 대하여 a=bq+r이면 G(a,b)=G(b,r)가 성립한다.'라는 것이다. 따라서 이를 이용해 b가 0이 될 때가 while문을 반복하도록 해서 최대공약수를 구하도록 하였다.

최소공배수는 두 수의 곱에다가 최대공약수를 나누면 쉽게 구할 수 있다.