못생긴 숫자(Ugly Number) - n번째 못생긴 숫자 구하기 알고리즘

못생긴 숫자란 무엇일까요?

못생긴 숫자(Ugly Number)는 소인수가 오직 2, 3, 5로만 이루어진 양의 정수를 의미합니다. 예를 들어 1부터 15 사이에는 총 11개의 못생긴 숫자가 존재하는데, 바로 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15입니다.

반면 7, 11, 13은 자기 자신을 소인수로 가지는 소수이므로 못생긴 숫자에 해당하지 않습니다. 마찬가지로 14도 소인수 분해 시 7이 포함되기 때문에 못생긴 숫자에서 제외됩니다.

이번 글에서는 이러한 정의를 바탕으로 n번째 못생긴 숫자를 효율적으로 찾는 프로그램을 만들어 보겠습니다.

입력과 출력 형식

입력:
항 번호(term number)를 입력받습니다. 예: 10
출력:
10번째 못생긴 숫자는 12입니다.

알고리즘 설계

핵심 아이디어는 이미 구한 못생긴 숫자들에 2, 3, 5를 곱한 값 중 최솟값을 차례대로 선택하는 것입니다. 세 개의 포인터(i2, i3, i5)를 활용하면 중복 없이 오름차순으로 못생긴 숫자를 생성할 수 있으며, 시간 복잡도는 O(n)으로 매우 효율적입니다.

getUglyNumbers(n)

입력: 구하고자 하는 항의 개수 n

출력: n번째 못생긴 숫자

Begin
    크기가 n인 배열 uglyNum을 선언한다
    i2 := 0, i3 := 0, i5 := 0
    next2mul := 2, next3mul := 3, next5Mul := 5
    next := 1
    uglyNum[0] := 1

    for i := 1 to n, do
        next := next2Mul, next3Mul, next5Mul 중 최솟값
        uglyNum[i] := next
        if next = next2Mul, then
            i2 := i2 + 1
            next2mul := uglyNum[i2] * 2
        if next = next3Mul, then
            i3 := i3 + 1
            next3mul := uglyNum[i3] * 3
        if next = next5Mul, then
            i5 := i5 + 1
            next5mul := uglyNum[i5] * 5
    done
    return next
End

C++ 구현 예제

# include<iostream>
using namespace std;

int min(int x, int y, int z) {          //세 수 중 가장 작은 값 찾기
    if(x < y) {
        if(x < z)
            return x;
        else
            return z;
    }else {
        if(y < z)
            return y;
        else
            return z;
    }
}

int getUglyNum(int n) {
    int uglyNum[n];                     //못생긴 숫자를 저장할 배열
    int i2 = 0, i3 = 0, i5 = 0;

    //다음 배수 후보: 1*2, 1*3, 1*5

    int next2mul = 2;
    int next3mul = 3;
    int next5mul = 5;
    int next = 1;                       //첫 번째 못생긴 숫자는 1

    uglyNum[0] = 1;

    for (int i=1; i<n; i++) {
        next = min(next2mul, next3mul, next5mul);   //다음 못생긴 숫자 결정
        uglyNum[i] = next;

        if (next == next2mul) {
            i2++;                       //인수 2를 사용하는 포인터 증가
            next2mul = uglyNum[i2]*2;
        }

        if (next == next3mul) {
            i3++;                       //인수 3을 사용하는 포인터 증가
            next3mul = uglyNum[i3]*3;
        }

        if (next == next5mul) {
            i5++;                       //인수 5를 사용하는 포인터 증가
            next5mul = uglyNum[i5]*5;
        }
    }
    return next;                        //n번째 못생긴 숫자 반환
}

int main() {
    int n;
    cout << "Enter term: "; cin >> n;
    cout << n << "th Ugly number is: " << getUglyNum(n) << endl;
}

실행 결과

Enter term: 10
10th Ugly number is: 12

마무리

이 알고리즘은 매번 1부터 모든 수를 검사하는 브루트 포스 방식(O(n²) 이상)과 달리, 동적 계획법(DP) 개념을 활용해 O(n) 시간 안에 답을 구합니다. 세 포인터가 각각 2, 3, 5의 배수 후보를 관리하고, 항상 최솟값을 배열에 저장함으로써 중복과 누락 없이 못생긴 숫자를 순서대로 생성할 수 있다는 점이 핵심입니다.