두 수의 최소공배수(Least Common Multiple) 입력된 두 수의 배수 중
공통이 되는 가장 작은 숫자를 의미합니다.
예를 들어 2와 7의 최소공배수는 14가 됩니다.
정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중
공통이 되는 가장 작은 숫자가 됩니다.
n개의 숫자를 담은 배열 arr이 입력되었을 때
이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
// N개 수의 곱 / N개의 최대 공약수 => N개의 최소공배수
// 유클리드 호제법으로 최대공약수 구하기
function solution(arr) {
function gcd(a, b){
if (b === 0) {return a;}
return gcd(b, a % b);
}
return arr.reduce((acc, cur) => {
return (acc * cur) / (gcd(acc, cur));
})
}
두 수의 곱 / 두 수의 최대공약수 = 두 수의 최소공배수
인 것을 활용해서 풀이
// 최대 공약수를 구하는 함수
fuction gcd(a, b){
if (b === 0) return a;
return gcd(b, a % b);
}
즉, 재귀를 돌면서 a % b
의 값이 0
이 되는 순간의 a
를 return 하는 구조입니다
a와 b의 대소관계는 크게 신경 안써도 되는 함수입니다
예를 들어 a = 5
, b = 30
인 경우에는
5 % 30 = 5
이기 때문에 다음 재귀에서return gcd(30, 5)
로 들어가게 됩니다
입출력 예시 [2, 6, 8, 14]
를 이용해 설명해보겠습니다
return arr.reduce((acc, cur) => {
(acc * cur) / (gcd(acc, cur));
위 코드 에서 acc값을 따로 지정해주지 않았으므로
초기 acc값에는 arr[0]
이 들어갑니다. 순서대로 설명해보자면
1) arr[0] * arr[1] / gcd(arr[0], arr[1])
즉, 2와 6의 곱
을 2와 6의 최대공약수
로 나눠서 최소공배수를 구합니다
➡️ 2와 6의 최소공배수
:6
이 축적값인 acc
로 들어갑니다
2) acc * arr[2] / gcd(acc, arr[2])
6과 8의 최소공배수
: 24
3) acc * arr[3] / gcd(acc, arr[3])
24와 14의 최소공배수
: 168
최종적으로 [2, 6, 8, 14]
의 최소 공배수 168
을 구했습니다