Programmers | 유클리드 호제법, GCD/LCM

• GCD(Greatest common divisor): 최대공약수
• LCM(Least common multiple): 최소공배수
• 두 수의 곱은 GCD와 LCM의 곱과 같다.

프로그래머스 0단계 문제들을 구경하다가 분수의 덧셈 문제를 보고 쉽게 풀이가 떠오르지 않아서 당황했다. 최대공약수를 구하는 함수를 만들기 위해 유클리드 호제법을 다시 공부했는데, 예전에 풀었을 때보다 더 간단한 코드를 보고 1단계 문제 복습과 2단계 문제 풀이에 도전했다.

분수의 덧셈 (Lv.0)

(문제)

function solution(denum1, num1, denum2, num2) {
  let denum = denum1 * num2 + denum2 * num1; // 분자
  let num = num1 * num2; // 분모

  const getGCD = (a, b) => (b === 0 ? a : getGCD(b, a % b));
  const gcd = getGCD(denum, num);

  return [denum / gcd, num / gcd];
}

getGCD 함수에서 두 수를 받아 나머지(더 작은 수, b)가 0이 될 때 최대공약수인 a를 리턴하고, 0이 아니라면 다시 재귀적으로 getGCD를 호출한다.
최종적으로 기약분수를 만들기 위해 각 denum과 num에 구해둔 최대공약수 gcd를 나누면 된다.

최대공약수와 최소공배수 (Lv.1)

(문제)

예전 풀이

function solution(n, m) {
  const answer = [n, m];
  answer.sort((a, b) => a - b);
  let [num1, num2] = [n, m];
  let r = num2 % num1;

  const getAnswer = () => {
    while (r !== 0) {
      num2 = num1;
      num1 = r;
      r = num2 % num1;
    }
    return [num1, (n * m) / num1];
    // n * m === GCD(num1) * LCM 이므로
  };

  return r ? getAnswer() : answer;
}

이때는 큰 수num2에서 작은 수num1를 나눈 나머지(remainder)를 구하기 위해 오름차순 정렬도 해주었는데, 정렬을 안해도 상관없다.
왜냐하면 작은 수를 큰 수로 나는 나머지는 작은 수 그대로기 때문에 num1과 num2의 자리가 바뀌게 되어 의도대로 동작하게 된다.
분수의 덧셈 풀이에서 활용한 getGCD 함수를 써서 코드를 아래처럼 줄일 수 있었다.

풀이 개선

function solution(n, m) {
  const getGCD = (a, b) => (b === 0 ? a : getGCD(b, a % b));
  const gcd = getGCD(n, m);
  return [gcd, (n * m) / gcd];
}

N개의 최소공배수 (Lv.2)

(문제)

시행착오

function solution(arr) {
  let answer = 1;
  let gcd = arr[0];
  const getGCD = (a, b) => (b === 0 ? a : getGCD(b, a % b));

  for (let i = 1; i < arr.length; i++) {
    gcd = getGCD(gcd, arr[i]);
  }

  arr.forEach(v => (answer *= v / gcd));
  return answer * gcd;
}

위 코드로 테스트케이스만 통과했다. 문제 이해도가 낮아 N개 수들의 최대공약수를 구해두고 활용하려고 했었다.
reduce를 사용해서 그때그때 두 수의 최대공약수를 나누어줌으로써 모든 수들의 최소공배수를 구했다.

통과

function solution(arr) {
  const getGCD = (a, b) => (b === 0 ? a : getGCD(b, a % b));
  return arr.reduce((acc, cur) => acc * (cur / getGCD(acc, cur)));
}