프로그래머스 레벨 2의 12953번 문제는 N개의 최소공배수를 구하는 문제다. 최소공배수는 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미한다. 예를들어 2와 7의 최소공배수는 14가 된다.
[2와 7의 최소공배수]
- 2의 배수: 2, 4, 6, 8, 10, 12, 14, ...
- 7의 배수: 7, 14, 21, 28, 35, 42, 49, ...
주어진 배열(arr)에서 가장 큰 수의 배수를 나머지 요소와 나눴을 때 모두 0이 되는 수를 찾는 방법으로 풀었지만, 매번 큰 수를 제외한 배열의 모든 숫자를 하나씩 나눠봐야 하기 때문에 효율적이지 않다. 배열 정렬을 제외하고 배열 길이가 n, while문의 반복 횟수가 x이라고 했을 때 시간복잡도는 O(n * 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)이다.
[12와 15의 최대 공약수]
- 12의 약수: 1, 2, 3, 4, 6, 12
- 15의 약수: 1, 3, 5, 15
12, 15의 공통 약수는 1, 3이고 가장 큰 수는 3이므로 최대공약수는 3
<aside>
<img src="/icons/search_gray.svg" alt="/icons/search_gray.svg" width="40px" /> mod는 나머지 연산을 의미한다. 자바스크립트에서 % 연산자와 동일하다.
</aside>
유클리드 호제법은 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의 최대공약수를 좀 더 쉽게 확인할 수 있을 것이다.
*<수학의 숨은 원리> 中*
[48(a)과 18(b)의 최대공약수]
- f(48, 18): 18(b), 12(48 % 18)의 최대공약수는 48(a)과 18(b)의 최대공약수와 동일하다
- f(18, 12): 12(b), 6(18 % 12)의 최대공약수는 18(a)과 12(b)의 최대공약수와 동일하다
- f(12, 6) : 12(a) % 6(b)가 0이므로 두 수의 최대공약수는 6(b)
참고로 a가 b보다 작다면, 항상 첫 번째 재귀 호출에서 a와 b의 위치가 바뀐다. 따라서 두 인자의 순서는 중요하지 않다.
- f(18, 48) -> 48(b), 18(18 % 48)
- f(48, 18) -> 18(b), 12(48 % 18)