[Programmers] level 1: 최대공약수와 최대공배수 by JavaScript

 이번 문제는 아래 포스팅을 참고하여 작성하였습니다.

 

• Lulu 님의 포스팅

JavaScript로 최대공약수(GCD), 최소공배수(LCM) 구하기

---

 이번 문제는 유클리드 호제법이나 반복문을 통해 풀 수 있다. 먼저 반복문을 활용하여 최대공약수 및 최소공배수를 구하는 법부터 설명하겠다. 반복문으로 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(n, m)까지 모든 정수로 n과 m을 나눠보는 방식이다. 이렇게 나눴을 때 n과 m 모두 나눠 떨어지는 수가 바로 최대공약수이다. 최소공배수는 while 반복문을 통해 변수를 1씩 증가시키면서 증가되는 변수가 n과 m 모두 나눠떨어질 때 그 변수가 바로 두 수 의 최소공배수가 된다. 

 유클리드 호제법의 기본 원리는 n을 m으로 나눈 나머지를 r이라고 했을 때 gcd(n, m) = gcd(m, r)이라는 것이다. 이때 r이 0이라면 그 시점의 m이 바로 n과 m의 최대공약수가 된다. 예를 들어 n을 24, m을 16이라고 가정하면

gcd(24, 16) → gcd(16, 8) → gcd(8, 0)  ∴ gcd = 8

위와 같이 계산이 되어 두 수의 최대공약수는 결과적으로 8이 나온다. 이를 코드로 나타내면

const getGcd = (n, m) => m === 0 ? m : getGcd(n, n % m);

 따라서 m이 0이 될 때까지 재귀함수를 반복하여 0이 되는 순간의 m을 반환하고, 0이 아니라면 첫 번째 인자로 n, 두 번째 인자로 n과 m의 나머지를 전달하는 것이다.

 최소공배수는 최대공약수를 활용하여 구할 수 있다. 이를 식으로 나타내면

lcm = gcd * (n / gcd) * (m / gcd) // n * m = gcd * lcm
=> lcm = (n * m) / gcd

 

Solutions

function solution(n, m) {
  /* Loop Ver. */
  const gcd = getGcd(n, m);
  const lcm = getLcm(n, m);
  return [gcd, lcm];

  /* Euclidean Algorithm */
  const gcd = (n, m) => (n % m === 0 ? m : gcd(m, n % m));
  const lcm = (n, m) => (n * m) / gcd(n, m);
  return [gcd(n, m), lcm(n, m)];
}

function getGcd(n, m) {
  // 최대공약수
  let gcd = 1;
  for (let i = 2; i <= Math.min(n, m); i++) {
    if (n % i === 0 && m % i === 0) gcd = i;
  }
  return gcd;
}

function getLcm(n, m) {
  // 최소공배수
  let lcm = 1;
  while (true) {
    if (lcm % n === 0 && lcm % m === 0) break;
    lcm++;
  }
  return lcm;
}