오늘 코테 공부를 하다가 프로그래머스에서 N개의 최소공배수
라는 문제를 풀었다. 하지만 이해가 안되서 찾아보니 유클리드 호제법을 사용하면 쉽게 문제를 해결 할 수 있다는 점을 알게 되었다.
✅최소 공배수를 구하려면?
두수의 곱 / 최대 공약수
✅최대 공약수를 구하려면?
유클리드 호제법
두개의 숫자 a, b (a > b) 가 존재 합니다.
case1. b 가 0 이면 a 출력 후 종료
case2. a 가 b 로 나누어 떨어지면 b 출력 후 종료
case3. a 가 b 로 나누어 떨어지지 않으면, a 를 b 로 나눈 나머지를 새롭게 a 에 대입한 후, a 와 b를 바꿈 -> case2 로 돌아감
// 최대 공약수
const gcd = (a,b) => {
if(b === 0){ // case1
return a;
}else if(a%b === 0){ // case2
return b;
}else{ // case3
return gcd(b, a%b);
};
};
// 최소 공배수
const lcm = (a,b) => {
return (a*b) / gcd(a,b);
};
function solution(arr){
let answer = 1;
for (let i = 0; i < arr.length; i++) {
answer = lcm(answer, arr[i]);
};
return answer;
};