JavaScript로 구하는 최대공약수와 최소공배수 (GCD / LCM)

최대공약수와 최소공배수란?

최대공약수(GCD, Greatest Common Divisor)는 두 수가 공통으로 가지는 약수 중 가장 큰 값을 의미합니다. 예를 들어 12와 18의 공약수는 1, 2, 3, 6이며, 그중 가장 큰 수는 6이므로 GCD는 6입니다.

반대로, 최소공배수(LCM, Least Common Multiple)는 두 수가 공통으로 가지는 배수 중 가장 작은 값을 말합니다. 같은 예시에서 12의 배수는 12, 24, 36, 48..., 18의 배수는 18, 36, 54..., 공통으로 나오는 배수 중 가장 작은 값은 36이므로 LCM은 36입니다.

이 두 개념은 수학적 문제 풀이뿐만 아니라, 시간 계산, 주기 분석, 배치 문제 등 여러 실제 코딩 문제에 자주 활용됩니다.

---

유클리드 호제법을 이용한 최대공약수(GCD) 계산

최대공약수를 구하는 데 가장 널리 사용되는 방법은 유클리드 호제법입니다. 두 수 a, b에서 a를 b로 나눈 나머지를 r이라 할 때, GCD(a, b)는 GCD(b, r)과 같다는 성질을 이용한 재귀적 접근 방식입니다.

자바스크립트 코드 예제

function gcd(a, b) {
  if (b === 0) return a;
  return gcd(b, a % b);
}

console.log(gcd(12, 18)); // 6

작동 흐름 설명

• 12와 18의 GCD를 구하는 과정:
  • gcd(12, 18) → gcd(18, 12)
  • gcd(18, 12) → gcd(12, 6)
  • gcd(12, 6) → gcd(6, 0)
  • b가 0이므로 최종 결과는 6

재귀적 구조를 이해하면 반복적인 나머지 연산을 통해 최대공약수가 도출된다는 점을 쉽게 파악할 수 있습니다.

---

최소공배수(LCM) 구하기

최소공배수는 두 수의 곱을 최대공약수로 나눈 값으로 구할 수 있습니다. 이 공식은 수학적으로도 증명된 안정적인 방식입니다.

공식

LCM(a, b) = (a * b) / GCD(a, b)

자바스크립트 코드 예제

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

console.log(lcm(12, 18)); // 36

작동 흐름 설명

• gcd(12, 18) → 6
• 12 * 18 = 216
• 216 / 6 = 36 → 최소공배수

이 방식은 간단하면서도 효율적이기 때문에 알고리즘 문제에서 자주 사용됩니다.

---

GCD와 LCM 함께 구하기

아래는 두 수의 최대공약수와 최소공배수를 동시에 구하는 함수 예제입니다:

function getGcdLcm(a, b) {
  const resultGcd = gcd(a, b);
  const resultLcm = (a * b) / resultGcd;
  return {
    gcd: resultGcd,
    lcm: resultLcm
  };
}

console.log(getGcdLcm(24, 36));
// { gcd: 12, lcm: 72 }

이와 같이 두 값을 함께 구하면 효율적이고, 코드의 응집도도 높아집니다.

---

시간 복잡도 분석

• 최대공약수 (유클리드 호제법): O(log(min(a, b)))
• 최소공배수: GCD를 활용하므로 전체 시간 복잡도는 GCD와 동일한 수준

즉, 매우 빠르고 안정적으로 두 수의 최대공약수와 최소공배수를 구할 수 있습니다.

---

마무리 및 추천 자료

최대공약수와 최소공배수는 수학과 컴퓨터 알고리즘 사이의 연결 고리를 이해하기에 좋은 주제입니다. 이 개념은 알고리즘 테스트, 시간 단위 문제, 주기적 반복 처리 등에서 자주 등장하며, 빠르고 정확한 구현이 중요합니다.

아래는 수학 기반 알고리즘 학습과 연습에 도움이 되는 무료 리소스입니다:

• 프로그래머스 수학 알고리즘 강의
• LeetCode Math 문제 모음
• replit JavaScript 실습 플랫폼