[TIL] 유클리드 호제법

오늘 코테 공부를 하다가 프로그래머스에서 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;
};