1. 문제 정의
최소 공배수(Least Common Multiple, LCM)란 두 개체 이상의 정수의 배수 중에서 가장 작은 공통 배수를 의미합니다.
예를 들어, 4와 5의 최소 공배수는 20입니다. 이는 4의 배수(4, 8, 12, 16, 20, …)와 5의 배수(5, 10, 15, 20, …)에서 공유되는
가장 작은 수이기 때문입니다. 본 강좌에서는 자바스크립트를 이용하여 주어진 두 수의 최소 공배수를 구하는 문제를 해결해보겠습니다.
2. 문제 설명
다음 두 정수를 입력받아 최소 공배수를 반환하는 함수를 작성하세요.
함수 시그니처: function lcm(a: number, b: number): number
입력:
- 2개의 정수 a, b (1 ≤ a, b ≤ 106)
출력:
- a와 b의 최소 공배수
예제:
- 입력: 4, 5 => 출력: 20
- 입력: 15, 20 => 출력: 60
- 입력: 7, 5 => 출력: 35
3. 알고리즘 접근 방법
최소 공배수를 구하는 방법은 여러 가지가 있습니다. 하지만 가장 일반적인 방법 중 하나는 최대 공약수(Greatest Common Divisor, GCD)를 이용한
방법입니다. 최소 공배수는 다음과 같은 공식으로 계산할 수 있습니다:
LCM(a, b) = (a * b) / GCD(a, b)
여기서 GCD를 구하는 효율적인 알고리즘 중 하나는 유클리드 호제법입니다.
유클리드 호제법은 두 정수의 GCD를 다음과 같은 방식으로 계산합니다:
- a를 b로 나눈 나머지를 r이라고 할 때, GCD(a, b) = GCD(b, r) 이 성립합니다.
- r이 0일 때, b가 바로 GCD입니다.
이제 이러한 논리를 바탕으로 자바스크립트로 LCM을 구하는 함수를 구현해보겠습니다.
4. 코드 구현
function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
function lcm(a, b) {
return (a * b) / gcd(a, b);
}
// 테스트 케이스
console.log(lcm(4, 5)); // 20
console.log(lcm(15, 20)); // 60
console.log(lcm(7, 5)); // 35
위의 코드는 GCD를 계산하고, 이를 이용하여 LCM을 계산하는 방식으로 구현되었습니다.
gcd 함수는 a와 b의 GCD를 반환합니다. lcm 함수는 두 수의 LCM을 계산하여 반환합니다.
5. 코드 설명
gcd 함수:
- 이 함수는 두 개의 정수를 인자로 받아 GCD를 계산합니다.
- while 루프를 이용하여 b가 0이 아닐 때까지 반복합니다.
- 각 반복에서 a를 b로 나눈 나머지를 구하고, a에는 b 값을, b에는 나머지 값을 할당합니다.
- b가 0이 되면 a에는 GCD 값이 저장되어 있으므로 이를 반환합니다.
lcm 함수:
- 이 함수는 두 개의 정수를 인자로 받아 LCM을 계산합니다.
- GCD(a, b)를 호출하여 GCD 값을 구하고, 이를 바탕으로 LCM(a, b)를 계산하여 반환합니다.
6. 최적화 & 고려사항
위의 알고리즘은 효율적입니다. GCD는 O(log(min(a, b)))의 시간 복잡도를 가지므로, LCM 계산에 필요한 시간도 최소화됩니다.
하지만 다음과 같은 사항도 고려해야 합니다:
- 음수 처리: 문제에서는 정수의 범위가 1 이상으로 제한되어 있지만, 실제 사용 시 음수를 처리할 수 있도록 예외 처리를 추가하는 것이 좋습니다.
- 최대값 처리: a와 b의 곱이 매우 커질 수 있으므로, 계산시 오버플로우가 발생할 수 있습니다. 이 경우 BigInt처럼 큰 숫자를 처리할 수 있는 방법을 고려해야 합니다.
7. 결론
본 강좌에서는 두 정수의 최소 공배수를 구하는 알고리즘을 공부해 보았습니다. 유클리드 호제법을 사용하여 효율적으로 GCD를 구하고,
이를 통해 LCM을 계산하는 방법을 배웠습니다. 이러한 알고리즘은 다양한 실전 문제에서 유용하게 사용될 수 있습니다.
다음 강좌에서는 또 다른 알고리즘 주제를 다루도록 하겠습니다. 감사합니다.