[Algorithm] 최대공약수와 최소공배수 구하기

초반에 레벨1 문제 풀었을때, 너무 오래 잊고있던 개념을 만나서 당황했었는데
이후로도 여러 문제에서 필요한 것 같아서 복습할겸 다시 정리하게 되었다.
처음에는 그냥 반복문으로 문제를 해결했는데,
유클리드 호제법 이라는 알고리즘도 공부해서 기록해본다.

최대공약수와 최소공배수

최대공약수는 두 수를 딱 떨어지게 나눌 수 있는 수(약수)들 중 공통된 가장 큰 수이다.
4 1, 2, 4
12 1, 2, 3, 4, 6, 12

최소공배수는 두 수의 배수들 중 공통된 가장 작은 수이다.
4 4, 8, 12, 16, 20 …
12 12, 24, 36, 48 …

최대공약수 구하기

2부터 a와 b중 더 작은 수 까지의 숫자들로 a와 b를 쭉 나눴을때
둘 다 나머지가 0이되는 숫자를 gcd라는 변수에 저장해서
마지막에 남는 가장 큰 수가 최대공약수가 된다.

function getGCD(a, b) {
  let gcd = 0;

  for (let i = 2; i < Math.min(a, b); i++) {
    if (a % i == 0 && b % i == 0) {
      gcd = i;
    }
  }

  return gcd;
}

최소공배수 구하기

이번에는 lcm 값이 나올때까지 계속 반복하는 while 문을 활용한다.
a와 b가 모두 나누어떨어지는 수가 나올때까지 lcm값을 1씩 증가시키면서 확인하고
모두 나누어떨어지는 수를 찾으면 값을 리턴 후 반복문을 종료한다.

function getLCM(a, b) {
  let lcm = 1;

  while (true) {
    if (lcm % a == 0 && lcm % b == 0) {
      return lcm;
    }
    lcm++;
  }
}

유클리드 호제법을 활용해 최대공약수 구하기

그냥 반복문으로 최대공약수를 구할때는 숫자가 클수록 절차가 많아진다.
유클리드 호제법을 활용하면 더욱 효율적으로 최대공약수를 구할 수 있다.

유클리드 호제법 개념
a와 b를 나눈 나머지값을 r이라하고, b를 다시 r로 나눠 r2를 구하고,
r을 다시 r2로 나눠 r3를 구하는 과정을 반복한다.
나머지가 0이 되었을때 마지막에 나누는 수로 사용한 수가 최대공약수이다.

650 % 120 = 50
120 % 50 = 20
50 % 20 = 10
20 % 10 = 0 // 650과 120의 최대공약수는 10이다.

위의 개념대로 나머지값을 반복해서 나누는 알고리즘을 자바스크립트 코드로 표현하면 아래와 같다.

function getGCD(a, b) {
  return a % b == 0 ? b : getGCD(b, a % b);
}

최대공약수 이용해서 최소공배수 구하기

a와 b를 곱한 수는 최대공약수와 최소공배수를 곱한 수와 같다는 공식을 활용하면
반복문을 사용하지 않고 더 간단한 코드로 표현할 수 있다.

lcm * gcd = a * b 는 곧
lcm = (a * b) / gcd 으로 표현할 수 있으므로

function getLCM(m, n) {
  let gcd = (a, b) => (a % b == 0 ? b : gcd(b, a % b));
  return (m * n) / gcd(m, n);
}

도움 받은 글