📕 문제
문제설명
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한조건
- arr은 길이 1이상, 15이하인 배열입니다.
- arr의 원소는 100 이하인 자연수입니다.
입출력 예
| arr | result |
|---|---|
| [2,6,8,14] | 168 |
| [1,2,3] | 6 |
🤔 고민과정
- 최소공배수를 구하는 방법을 찾다가, 유클리드 호제법을 이용하는 것이 가장 효율적이라는 결론에 도달했다. 유클리드 호제법에 대해 공부해보자.
▶ 유클리드 호제법(Euclidean Algorithm)
두 수의 최대공약수(GCD)를 구하는 효율적인 알고리즘입니다. 이 방법은 나눗셈의 성질을 이용해 반복적으로 두 수를 나누고, 나머지가 0이 될 때까지 그 과정을 이어가는 방식입니다.
구체적인 절차는 다음과 같습니다:
- 두 수 A와 B가 있을 때, A를 B로 나눈 나머지를 구합니다. (A > B라고 가정)
- A를 B로 나눈 나머지를 R이라고 할 때, A 대신 B를, B 대신 R을 사용합니다.
- 나머지가 0이 될 때까지 이 과정을 반복합니다.
- 마지막으로 B가 0이 되었을 때, 그 직전의 나머지 값이 A와 B의 최대공약수(GCD)입니다.
최소공배수(LCM)는 두 수 A와 B의 곱을 그들의 최대공약수(GCD)로 나누면 구할 수 있습니다.
즉, A와 B의 곱을 최대공약수로 나누면, 두 수의 공통 배수 중에서 가장 작은 값인 최소공배수를 구할 수 있습니다.
따라서, 유클리드 호제법으로 최대공약수(GCD)를 구한 뒤, 이를 이용해 최소공배수(LCM)도 쉽게 계산할 수 있습니다.
✅ 결과물
// 최대공약수(GCD)
const gcd = (a, b) => {
// A를 B로 나눈 나머지를 R, A 대신 B를, B 대신 R을 사용
return b === 0 ? a : gcd(b, a % b);
};
// 최소공배수(LCM)
const lcm = (a, b) => {
return (a * b) / gcd(a, b);
};
function solution(arr) {
// 최소공배수를 저장, 처음엔 1로 시작
let answer = 1;
for (let i = 0; i < arr.length; i++) {
// answer와 arr[i]의 최소공배수를 구해서 다시 answer에 저장
answer = lcm(answer, arr[i]);
}
return answer;
}