Least Common Multiple Explanation

Problem Summary

Write a function that returns the least common multiple of two numbers.

Detailed Explanation

이 문제는 **GCD를 활용**하여 최소공배수를 구하는 방법을 학습합니다. ## 핵심 개념: 최소공배수 (LCM) 최소공배수는 두 수의 공통된 배수 중 가장 작은 수입니다. ### GCD와 LCM의 관계 ```javascript LCM(a, b) = (a * b) / GCD(a, b) ``` ### 접근 방법 ```javascript function lcm(a, b) { const gcd = (x, y) => y ? gcd(y, x % y) : x; return (a * b) / gcd(a, b); } ``` ### 왜 이 공식이 성립하는가? - a = GCD * m, b = GCD * n (m, n은 서로소) - LCM = GCD * m * n - a * b = GCD * m * GCD * n = GCD² * m * n - LCM = (a * b) / GCD ### 예시: LCM(4, 6) - GCD(4, 6) = 2 - LCM = (4 * 6) / 2 = 12 ### 오버플로우 방지 큰 수에서는 `(a / gcd) * b`로 계산하면 더 안전합니다.

Solution Code

solution.js

function lcm(a, b) {
  const gcd = (x, y) => y ? gcd(y, x % y) : x;
  return (a * b) / gcd(a, b);
}

Key Concepts from This Problem

1. 최소공배수

2. GCD 활용

3. 수학 공식

4. 오버플로우 방지

Common Mistakes

✗ a * b가 큰 경우 오버플로우가 발생할 수 있습니다

✗ GCD가 0이면 나눗셈 오류가 발생합니다

✗ GCD 함수를 먼저 정의하거나 내부에 구현해야 합니다

Hints

Hint 1: LCM = (a * b) / GCD(a, b)

Complexity Analysis

Time Complexity

O(log(min(a,b)))

Space Complexity

O(1)

Uses almost no additional memory

Related Tags

#알고리즘 #LCM #수학