📙

GCD / LCM

용어 알고가기

•

약수 : 어떤 수를 나누어 떨어지게 하는 수

•

배수 : 어떤 수의 1, 2, 3, ...n 배하여 얻는 수

•

공약수 :  둘 이상의 수의 공통 약수

•

공배수 : 둘 이상의 수의 공통 배수

•

최대 공약수 : 둘 이상의 공약수 중 최대인 수

•

최소 공배수 : 둘 이상의 공배수 중 최소인 수

약수 구하기

n의 약수를 구하려면 어떻게 해야할까?

쉽게 생각해본다면 n을 1부터 n까지의 수로 한번씩 나눠서 확인해볼 수 있다.

function getDivisor(n) {
  const result = [];
	for (let i = 1; i < n; i++) {
    if (n % i === 0) result.append(i);
  }
  return result;
}
JavaScript
복사

위와 같은 방법도 있지만 더 효율적으로 구하는 방법을 생각해보자

임의의 자연수 N의 약수들 중에서 두 약수의 곱이 N이 되는 약수 A와 약수 B는 반드시 존재한다

⇒ 자연수 N의 제곱근까지의 약수를 구하면 그 짝이 되는 약수는 자동으로 구해진다.

function getDivisor(n) {
  const result = [];
  const resultBack = [];
	for (let i = 1; i < n ** (1 / 2); i++) {
    if (n % i === 0) {
      result.push(i);
      if (i * i !== n) result.unshift(n / i);
    }
  }
  return result.concat(resultBack);
}
JavaScript
복사

위 코드는 O(

\sqrt{n}

)의 시간복잡도를 가짐

GCD 최대 공약수

Greatest Common Divisor

둘 이상의 공약수 중, 최대인 수

유클리드 호제법

a를 b로 나눈 나머지를 r이라고 한다면

a와 b의 최대공약수와 b와 r의 최대공약수가 같고 r이 0일 때의 b가 최대공약수이다.

GCD(a, b) = GCD(b, a % b)

따라서 아래와 같이 코드를 작성할 수 있다.

let getGCD = (a, b) => (b > 0 ? getGCD(b, a % b) : a);
JavaScript
복사

a < b 이더라도 getGCB(a, a % b = a) 이므로 자동 스왑된다.

LCM 최소 공배수

Least Common Multiple

둘 이상의 공배수 중, 최소인 수

최소 공배수는 최대 공약수를 사용해서 구할 수 있다.

a * b = gcd(a, b) * lcm(a, b) 이므로

⇒ lcm(a, b) = (a * b) / gcd(a, b)

let getGCD = (a, b) => (b > 0 ? getGCD(b, a % b) : a);
let getLCM = (a, b, gcd) => (a * b) / gcd;
const solution = (a, b) => {
  let gcd = getGCD(a, b);
	return getLCM(a, b, gcd);
}
JavaScript
복사