[Algorithm] 유클리드 알고리즘 / 소인수분해로 최소공배수 최대공약수 계산하기

N개의 최소공배수

---

프로그래머스 레벨 2의 12953번 문제는 N개의 최소공배수를 구하는 문제다. 최소공배수는 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미한다. 예를들어 2와 7의 최소공배수는 14가 된다.

 

주어진 배열(arr)에서 가장 큰 수의 배수를 나머지 요소와 나눴을 때 모두 0이 되는 수를 찾는 방법으로 풀었지만, 매번 큰 수를 제외한 배열의 모든 숫자를 하나씩 나눠봐야 하기 때문에 효율적이지 않다. 배열 정렬을 제외하고 배열 길이가 n, while문의 반복 횟수가 x이라고 했을 때 시간복잡도는 $O(n \cdot x)$가 된다.

function solution(arr) {
  const sortedArray = arr.sort((a, b) => b - a);
  const [biggest, ...rest] = sortedArray;

  const isDivisible = (target) => rest.every((n) => target % n === 0);

  let lcmFound = false;
  let multiplier = 1;
  let leastCommonMultiple = -1;

  while (!lcmFound) {
    const currentNum = biggest * multiplier;
    lcmFound = isDivisible(currentNum);
    if (lcmFound) leastCommonMultiple = currentNum;
    multiplier++;
  }

  return leastCommonMultiple;
}

solution([1, 2, 3]); // 6
// 1: 1, 2, 3, 4, 5, 6, ...
// 2: 2, 4, 6, 8, ...
// 3: 3, 6, 9, 12, ...

 

유클리드 알고리즘

---

다른 사람의 코드를 살펴보던 중, 유클리드 알고리즘을 사용하면 (대략)로그 시간 복잡도로 문제를 해결할 수 있는 것을 발견했다. a, b 두 수의 곱을, 두 수의 최대공약수로 나눠서 최소공배수를 계산하는 방법이다.

// 최대공약수(Greatest Common Divisor, GCD) 찾기
function gcd(a, b) {
  if (b === 0) return a;
  return gcd(b, a % b);
}

// 최소공배수(Least Common Multiple, LCM) 찾기
function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

function solution(arr) {
  let result = arr[0];

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

  return result;
}

solution([1, 2, 3]); // 6

 

위 코드에서 최대공약수를 계산하는 부분에 유클리드 알고리즘이 적용됐다. 최대공약수는 두 수(혹은 그 이상)가 공통으로 가지는 약수 중 가장 큰 수를 의미한다(두 수가 동시에 나누어 떨어지는 가장 큰 수). 약수는 어떤 수를 나누어 떨어지게 하는 수(나머지 0)이다.

 

💡 mod는 나머지 연산을 의미한다. 자바스크립트에서 % 연산자와 동일하다.

 

유클리드 호제법은 a, b 두 수가 주어졌을 때 b와 a mod b의 최대공약수는 a, b의 최대공약수와 동일하다는 특성을 이용한 방법이다. 즉, 두 정수의 최대공약수는 동일하게 유지하면서, 두 정수를 작게 만드는 원리라고 볼 수 있다.

예를 들어, 172와 36을 보자. 두 수의 최대공약수는 4이다. 4와 24의 최대공약수도 4이다.
4와 24의 최대공약수는 최대 4를 넘을 수 없다. 24= 4 · 6. 따라서 두 수의 최대공약수는 4이다.
172와 36의 최대공약수가 4임을 확인하는 것보다 4와 24의 최대공약수가 4임을 보이는 것이 더 쉽다.
왜 그럴까? 그것은 172, 36보다 4, 24의 크기가 더 작기 때문이다.
따라서 172와 36의 최대공약수를 유지하면서, 두 수 172, 36을 더 작게 만든다면,
172와 36의 최대공약수를 좀 더 쉽게 확인할 수 있을 것이다.

<수학의 숨은 원리> 中

 

 

참고로 a가 b보다 작다면, 항상 첫 번째 재귀 호출에서 a와 b의 위치가 바뀐다. 따라서 두 인자의 순서는 중요하지 않다.

 

최대공약수와 최소공배수의 관계

---

최대공약수(GCD)와 최소공배수(LCM)는 특별한 관계를 갖는다. a, b 두 수가 주어졌을 때 a,b의 최대공약수와 최소공배수를 곱한 값은 a, b를 곱한 값과 동일하다.

 

$$a \times b=GCD(a,b) \times LCM(a,b)$$

 

예를들어 a가 48, b가 18라면, 이 두 수의 곱은 864이고, 이는 두 수의 최대공약수 6과 최소공배수 144를 곱한 값과 같다.

 

$$\begin{align*}a &= 48, \quad b = 18 \\a \times b &= 864 \\\text{GCD}(48, 18) &= 6 \\\text{LCM}(48, 18) &= 144 \\\text{GCD}(48, 18) \times \text{LCM}(48, 18) &= 864\end{align*}$$

 

이러한 관계를 이용하여 두 수의 최대공약수를 알고 있을 때 최소공배수를 더 쉽게 찾을 수 있다. 그 반대의 경우도 마찬가지다.

 

❶ 최대공약수를 알고 있을 때 최소공배수 구하기

$$LCM(a,b)=\frac{a \times b}{GCD(a,b)}$$

 

❷ 최소공배수를 알고 있을 때 최대공약수 구하기

$$GCD(a,b)=\frac{a \times b}{LCM(a,b)}$$

 

위 내용을 코드로 풀어보면 아래와 같다. 48(a)과 18(b)의 최대공약수 6을 알고 있을 때 이 둘의 곱 864를 최대공약수 6으로 나누면 최소공배수를 계산할 수 있다.

// 최대공약수(Greatest Common Divisor, GCD) 찾기
function gcd(a, b) {
  if (b === 0) return a;
  return gcd(b, a % b);
}

// 최소공배수(Least Common Multiple, LCM) 찾기
function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

 

소인수분해로 GCD / LCM 계산하기

---

소인수분해는 주어진 정수를 더 이상 나눌 수 없는 소수들의 곱으로 표현하는 것을 의미한다.

 

소수는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 자연수로 2, 3, 5, 7, 11 등이 있다. 소인수는 어떤 정수를 소수들의 곱으로 표현할 때 사용되는 소수들을 말한다. 예를들어 48을 소인수분해하면 2⁴ × 3이 되고, 이때 소인수는 2, 3이다.

 

소인수분해는 가장 작은 소수인 2부터 시작하여 주어진 숫자를 나누고, 그 결과값(몫)을 기록한다. 2로 더 이상 나누어 떨어지지 않으면 그 다음 소수인 3으로 나누기를 시도한다. 주어진 숫자를 더 이상 나눌 수 없을 때까지 이 과정을 반복한다.

48, 18 소인수분해 예시

아래는 주어진 정수 n의 소인수를 찾아 배열로 반환하는 함수. primeFactors 함수에서 remainder가 i로 나누어 떨어지지 않으면 i를 1씩 증가시키는데, 이때 i가 소수인지 따로 판별하지 않아도 된다.

const primeFactors = (n) => {
  const result = [];
  let remainder = n;
  let i = 2;

  while (remainder > 1) {
    if (remainder % i === 0) {
      result.push(i);
      remainder /= i;
    } else i++;
  }

  return result;
};

const getFactorsWithExponents = (n) => {
  const factors = primeFactors(n); // [ 2, 2, 2, 2, 3 ]
  return factors.reduce((acc, cur) => {
    acc[cur] = (acc[cur] ?? 0) + 1;
    return acc;
  }, {});
};

getFactorsWithExponents(48); // { 2: 4, 3: 1 } -> 2⁴ × 3

i가 소수가 아닌 경우, 예를 들어 4, 6, 8, 9 등의 숫자는 이미 이전 단계에서 해당 숫자들의 소인수(2, 3, ...)가 remainder를 나누었기 때문에 remainder는 더 이상 i로 나누어 떨어지지 않게 된다. 따라서 i가 소수가 아닌 숫자일 땐 자연스럽게 건너뛰게 된다.

 

최대공약수

소인수분해 결과를 활용하면 최대공약수(GCD)와 최소공배수(LCM)를 쉽게 찾을 수 있다.

두 수의 공통 소인수들 중에서, 최소 지수를 선택하여 곱한 값

 

 

const gcd = (a, b) => {
  const factorsA = getFactorsWithExponents(a); // { 2: 4, 3: 1 }
  const factorsB = getFactorsWithExponents(b); // { 2: 1, 3: 2 }
  let result = 1;

  for (const factor in factorsA) {
    // 프로토타입 체인으로 상속된 속성이 객체 속성인 것처럼 취급되는 것을 방지하기 위한 조건
    if (Object.hasOwn(factorsA, factor)) {
      const [A, B] = [factorsA[factor], factorsB[factor]];
      if (A && B) result *= factor ** Math.min(A, B);
    }
  }

  return result;
};

gcd(48, 18); // 6

 

🔍 Object.hasOwn, Object.prototype.hasOwnProperty 두 메서드는 객체가 특정 속성을 가지고 있는지 확인한다. 하지만 Object.hasOwn은 Object의 정적 메서드여서 오버라이딩(재정의) 이슈가 발생하지 않는다. 아래 예제에서 볼 수 있듯이 Object.prototype.hasOwnProperty는 오버라이딩된 메서드에 영향을 받아 예상대로 작동하지 않고 있다.

const user = {
  age: 30,
  hasOwnProperty: () => 'user에 정의된 hasOwnProperty',
  hasOwn: () => 'user에 정의된 hasOwn',
};

console.log(Object.hasOwn(user, 'age')); // true
console.log(user.hasOwnProperty('age')); // 'user에 정의된 hasOwnProperty'

 

최소공배수

두 수가 갖는 모든 소인수들 중에서, 최대 지수를 선택하여 곱한 값

 

 

const lcm = (a, b) => {
  const factorsA = getFactorsWithExponents(a); // { 2: 4, 3: 1 }
  const factorsB = getFactorsWithExponents(b); // { 2: 1, 3: 2 }
  let result = 1;

  const allFactors = { ...factorsA, ...factorsB }; // { 2: 1, 3: 2 }

  for (const factor in allFactors) {
    if (Object.hasOwn(allFactors, factor)) {
      const [A, B] = [factorsA[factor], factorsB[factor]];
      result *= factor ** Math.max(A ?? 0, B ?? 0);
    }
  }

  return result;
};

lcm(48, 18); // 144

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요