C++로 구현하는 못생긴 수(Ugly Number) 알고리즘

못생긴 수(Ugly Number)란?

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

반면 7, 11, 13은 자기 자신 외에 약수가 없는 소수이므로 못생긴 수에 해당하지 않으며, 14는 소인수 분해했을 때 7이 포함되기 때문에 역시 제외됩니다. 예를 들어 10번째 못생긴 수를 구하면 그 값은 12가 됩니다.

알고리즘

n번째 못생긴 수를 구하는 핵심 아이디어는 동적 계획법(Dynamic Programming)입니다. 이미 구한 못생긴 수에 각각 2, 3, 5를 곱한 값 중 가장 작은 것을 차례대로 선택하면서 배열을 채워 나갑니다.

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-1 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 << "항 입력: "; cin >> n;
   cout << n << "번째 못생긴 수는: " << getUglyNum(n) << endl;
}

실행 결과

입력:

10

출력:

항 입력: 10
10번째 못생긴 수는: 12

동작 원리 및 시간 복잡도

이 알고리즘은 세 개의 포인터(i2, i3, i5)를 사용하여 2, 3, 5를 각각 곱할 후보 못생긴 수의 위치를 추적합니다. 매 단계마다 세 후보 값 중 가장 작은 것을 배열에 저장하고, 해당 값을 만들어낸 포인터를 한 칸 앞으로 이동시킵니다.

이 방식 덕분에 같은 값이 중복 생성되지 않으면서 못생긴 수가 오름차순으로 순서대로 쌓이게 됩니다. 전체 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로, 모든 자연수를 하나씩 소인수분해하여 검사하는 브루트포스 방식보다 훨씬 효율적이라는 점이 가장 큰 장점입니다.