"소인수분해"
Ugly Numbers
직역하면 "못생긴 숫자들" 이 되는 Ugly Numbers 라는 것은 어떤 수를 소인수분해했을 때, 2, 3, 5 라는 소인수로만 이루어진 수를 말합니다. 한국어로 정의가 되어있는지 구글링해보았지만 딱히 발견하지는 못했습니다. 딱 하나 "심술쟁이 수"라고 번역이 된 것이 있긴 했는데 범용적으로 쓰이는 표현은 아닌 것 같네요.
대신에 원어 그대로 검색을 해보면 상당히 다양한 자료들을 발견할 수 있었는데요. 최소한 알고리즘 관련해서 범용적으로 쓰이는 표현인 것 같아 정리해보려고 합니다. 기본적인 개념은 소인수분해를 이해하는 수준이면 충분한 것 같구요. 소인수분해를 언제 배웠는지도 기억이 안 나는 관계로 소인수분해부터 짧게 짚어보고 넘어가겠습니다.
소인수분해
인수란 어떤 수의 몇 개의 수의 곱으로 표현할 때, 그 구성식의 각 요소들을 가리킵니다. 약수와도 비슷하다고 할 수 있는데요. 이렇게 해서는 어려우니 예시를 간단히 들어보겠습니다.
30 이라는 숫자를 여러 개의 수로 나누어 풀어본다면 2 * 3 * 5 라고 할 수 있겠죠. 아니면 6 * 5, 또는 15 * 2 라고 표현할 수도 있을 겁니다. 이 때 2, 3, 5, 6, 15 등을 인수라고 할 수 있는 것이고, 그 중에서도 소수인 인수들을 가리켜 소인수라고 할 수 있습니다.
소인수분해는 어떤 수를 가장 작은 소인수부터 나누어, 최종적으로 소수가 나올 때까지 해체(?) 하는 것을 말합니다. 보통 짝수는 일단 2부터 시작해서 나누기 시작하고, 짝수가 아니라면 3, 5, 7, 11 이렇게 올라가면서 소수로 나눠보게 되죠.
Ugly Numbers 알고리즘
주어진 수가 Ugly Numbers 에 해당하는지를 묻고 있다면 주어진 수를 소인수분해하고 소인수가 2, 3, 5로만 되어있는지를 확인하면 되겠죠. 반복문을 돌려가며 일단 주어진 수를 가장 작은 수인 2로부터 나누기 시작하고, 더 이상 2로 나누어 떨어지지 않으면 3으로, 그리고 5로 나누어보면 될 것 같습니다.
근데 이래서야 알고리즘 문제라고 하기엔 너무 단순한 것 같습니다. 알고리즘 문제들은 이렇게 쉽게 풀린 적이 없으니까요. 검색해보니 Ugly Numbers 와 관련된 알고리즘들은 Ugly Numbers 의 n 번째 수가 무엇인지를 묻는 문제인 경우가 많았습니다. 구글에서 "Ugly Numbers" 로 검색해서 나온 첫 번째 링크인 geeksforgeeks 에서도 n 번째 수를 묻고 있네요.
얼른 직관적으로 생각해서는 반복문을 돌려가며 숫자들을 소인수분해하는 아이디어를 떠올릴 수 있겠습니다만, 조금만 더 생각해보면 그다지 효율적인 아이디어는 아니라는 걸 알게 됩니다. 일단 모든 수를 다 파악해보아야 한다는 점 부터가 알고리즘 풀이에는 그다지 적절해보이지 않죠.
그 대신 모든 Ugly Numbers 는 2, 3, 5 의 곱으로 이루어져 있다는 점에 주목할 필요가 있습니다. 나누는 것이 아니라, 역으로 곱을 통해 Ugly Numbers 를 찾아나갈 수 있다는 것이죠. Ugly Numbers 에 2, 3, 5 를 곱해도 여전히 Ugly Numbers 가 될테니까요.
function UglyNumbers(N) {
const uglyNumbers = [1];
}링크에 보면 컨벤션으로 1 을 포함한다고 하니 Ugly Numbers를 담을 배열을 선언해주고 1 을 담아 초기화해줄 수 있겠습니다. 1 * 2 = 2 이니 배열에 들어갈 그 다음 숫자는 2 가 되겠네요. 마찬가지로 1 * 3 = 3 도 배열에 포함될테고 1 * 5 = 5 도 포함되겠네요.
여기에서 조금 까다로운 지점이 발생합니다. 이번 알고리즘의 핵심이기도 한데요. 주어진 숫자들에 2, 3, 5 를 한 번씩 곱해서 더 높은 Ugly Numbers 를 구할 수 있는데, 무조건 제일 낮은 숫자에 2, 3, 5 를 다 곱하는 것으로는 Ugly Numbers 를 구할 수 없다는 점입니다.
예를 들어봅시다. 1 이라는 숫자에 2, 3, 5 를 각각 곱해서 uglyNumbers 배열에 더하게 되면 [1, 2, 3, 5] 가 되겠죠. 근데 2 * 2 = 4 도 Ugly Numbers 이기 때문에 배열에 포함이 되어야 합니다. 1 이라는 숫자에 2, 3, 5 를 먼저 다 곱하고 배열에 추가해버리게 되면 4 라는 숫자를 놓칠 수 있다는 것이죠.
일단 다 진행하고 전체 배열에서 중복되는 수를 제거한 후 정렬하는 방법도 있겠습니다만, 애초부터 순서를 맞춰서 배열에 추가하는 방법은 없을까요? 그러기 위해서는
1. 어떤 수(Ugly Numbers)에 Ugly Numbers 를 이루는 소인수인 2 (3, 5 도 마찬가지로) 를 곱해서 그 결과가 추가되었다면 그 다음 숫자(Ugly Numbers)에 소인수 2 (3, 5) 를 곱해야 한다.
2. 이미 다음 숫자로 넘어가서 소인수를 곱한 수와, 기존에 아직 곱하지 못한 소인수가 남아있는 경우를 대조해서, 더 작은 것을 먼저 배열에 추가해주어야 한다.
이 두 가지를 만족해야 할 것 같습니다. 이를 코드로 정리하면 다음과 같이 되겠죠.
function UglyNumbers(n) {
const uglyNumbers = [1];
let idx2 = 0;
let idx3 = 0;
let idx5 = 0;
for(let i = 0; i < n; i++) {
const mulBy2 = uglyNumbers[idx2] * 2;
const mulBy3 = uglyNumbers[idx3] * 3;
const mulBy5 = uglyNumbers[idx5] * 5;
let nextUglyNum = Math.min(mulBy2, mulBy3, mulBy5);
uglyNumbers.push(nextUglyNum);
if (nextUglyNum === mulBy2) idx2++;
if (nextUglyNum === mulBy3) idx3++;
if (nextUglyNum === mulBy5) idx5++;
}
return uglyNumbers[n - 1];
}idx2 idx3 idx5 라는 인덱스를 담을 변수를 각각 선언해주고 이를 0으로 초기화했습니다. 만약 2라는 소인수를 곱해서 그 값이 배열에 추가되었다면 이제 해당하는 인덱스의 숫자에 2를 곱할 필요가 없기 때문에 맨 아래에서 인덱스 값을 하나씩 증가시켜 주고 있죠.
배열의 다음 값을 담을 nextUglyNum 변수는 기존의 숫자에 남아있는 소인수를 곱한 값과, 배열에 추가된 새로운 값에 소인수를 곱한 값을 서로 비교해, 더 작은 값을 먼저 추가해주도록 되어있습니다.
참고로 맨 아래에서 조건에 해당하는 모든 인덱스를 올려주는 것은 값이 중복될 수 있기 때문입니다. 예를 들어 2 * 3 === 3 * 2 이기 때문이죠.
이렇게 해서 Ugly Numbers 의 n 번째 숫자를 찾는 알고리즘에 대해 알아보았습니다.
