N개의 최소공배수
문제 설명
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한 사항
arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.
나의 풀이 (체점 통과 못함)
function solution(arr) {
let num = arr[0]
for(let i=1;i<arr.length;i++){
let mul = num * arr[i];
mul % 2 === 0 && mul / 2 !== 1 ? num = mul / 2
: num = (mul * arr[i])
}
return num;
}최소 공배수를 구하는 방법은 2가지가 있는데 이걸 어떻게 풀어볼까 종이에 끄적이면서 먼저 풀어보았다. 그 와중에 찾아낸 방법은 앞에 2개의 수의 최소공배수를 먼저 구하고 그 값을 또 뒤에 숫자와의 최소공배수를 구하고 해서 최종 최소공배수를 구하는 방법이다.
이러면 반복문 안에서도 가능할 듯 싶었다.
테스트는 통과하지만 뭐가 문제인지 체점에서 전부 에러가 뜬다.
실패했지만 이 방향성이 맞는듯 해서 일단 계속 이 방법으로 오늘 시간 날때마다 좀 더 고민을 해봐야겠다.
- 2022.11.16
유클리드 호제법으로 풀 수 있어 라는 말 한마디에 유클리드 호제법이 뭐야?? 하고 찾아보았다.
우선 호제법부터 쳐보았더니 유클리드 호제법이 바로 나왔다.
호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
출처:위키백과
유클리드 호제법을 유클리드 알고리즘이라고도 하는 걸 보니 호제법은 알고리즘이다 라고 이해해도 될 듯 하다.
그럼 이건 어떻게 써먹는 것인가
최소공배수 = 두 수의 곱 / 최대 공약수 공식을 이용해서 풀 수 있을 것 같다.
2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대 공약수와 같다.
이 말은 식으로 이렇게 나타낼 수 있다
//최대공약수
const gcd = (a, b) => {
while (b > 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
//최소공배수
const lcm = (a, b) => {
return (a * b) / gcd(a, b);
}최소공배수를 구하는 공식은 두 수를 곱한 값을 두 수의 최대공약수로 나눈 값과 같다.
const solution = arr => {
let answer = 1;
for (let i = 0; i < arr.length; i++) {
answer = lcm(answer, arr[i]);
}
return answer;
}이렇게까지 입력해주면 값을 구할 수 있다.
그런데 아직 다 이해를 하진 못했다... 알고리즘 잘하고싶다....
