[프로그래머스] N개의 최소공배수 (유클리드 호제법)

https://school.programmers.co.kr/learn/courses/30/lessons/12940

최대공약수, 최소공배수란

최대공약수(GCD) = 2부터 min(숫자1, 숫자2)까지 전부 나눠 떨어지는 최대 숫자

최소공배수(LCM) = 최대공약수 * (숫자1 / 최대공약수) * (숫자2 / 최대공약수)

 

두 자연수 a, b의 최대공약수 구하기 (a > b일때)

유클리드 호제법
큰 수가 작은 수를 나눈 나머지를  이용하여 최대공약수를 구하는 알고리즘이다.

 

 

[유클리드 호제법] 14, 8의 최대공약수는 2

 

 

1. 큰 수로 작은 수를 나눈다 (나머지 = remainder)

2. 나머지가 0이면 작은수가 최대공약수이다

2. 나머지가 0이 아니면 작은수와 나머지의 최대공약수를 구한다.gcd(작은수b, 나머지remainder)

 

function getGCD(a, b) {
  const remainder = a % b;  // 1번
  if (remainder === 0) return b;  // 2번
  return gcd(b, remainder);  // 3번
}

 

 

또한 이렇게도 표현 가능하다.

작은 수는 다음 gcd의 큰수가 되고, 큰 수를 작은 수로 나눈 나머지가 작은수가 된다.

 

function getGCD(a, b) {
  while (b > 0) {
    let smallerNum = b;
    b = a % b;
    a = smallerNum;
  }
  return a;
};

 

두 수 a, b의 최소공배수 구하기

 

최소공배수는 최대공약수를 이용하여 구할 수 있다.

최소공배수 = 최대공약수 * (a / 최대공약수) * (b / 최대공약수)
                  = a * b / 최대공약수

          

function getLCM(a, b) {
  return (a * b) / getGCD(a, b);
}

---

관련문제 풀어보기

 

https://school.programmers.co.kr/learn/courses/30/lessons/12953#

 

 

• 1번째 수와 2번째 수의 최소공배수를 구하고, 구한 최소공배수와 3번째 수의 최소공배수를 구한다. 이런식으로 N개까지 최소공배수를 구하면 그 수가 N개의 공통 최소공배수가 된다.
• 최소공배수 = a * b / 최대공약수
• 최대공약수는 유클리드 호제법으로 구한다.

function solution(arr) {
    arr.sort((a, b) => a-b);
    let lcm = 1;
    
    for (let i = 0; i < arr.length; ++i) {
        lcm = getLCM(lcm, arr[i]);  // 이전 최소공배수와 현재값의 최소공배수
    }
    return lcm;
}

// 최대공약수 구하기
function getGCD(a, b) {
    if (b === 0) return a;
    return getGCD(b, a%b);
}

// 최소공배수 구하기
function getLCM(a, b) {
    return (a*b)/getGCD(a, b);
}