C++에서 숫자가 a^b 형태의 거듭제곱으로 표현 가능한지 확인하는 방법

이 글에서는 주어진 숫자가 a^b와 같은 거듭제곱 형태로 표현될 수 있는지 확인하는 방법을 알아보겠습니다. 예를 들어 숫자 125는 5³으로 표현할 수 있지만, 91은 어떤 정수의 거듭제곱으로도 나타낼 수 없습니다.

알고리즘

핵심 아이디어는 간단합니다. 밑(base)이 될 수 있는 값 i를 2부터 √num까지 순회하면서, num을 i의 거듭제곱으로 나타냈을 때 지수가 정수에 가까운지 로그 함수를 이용해 검사하는 것입니다.

isRepresentPower(num):
Begin
    if num = 1, then return true
    for i := 2, i² <= num, increase i by 1, do
        val := log(num)/log(i)
        if val – int(val) < 0.0000000001, then return true
    done
    return false
End

여기서 log(num) / log(i)는 log_i(num), 즉 i를 밑으로 하는 num의 로그값을 의미합니다. 만약 num이 i의 정수 거듭제곱이라면 이 값은 정수가 되어야 하므로, 소수 부분이 충분히 작으면(부동소수점 오차를 고려해 약 10^-8 미만) 해당 숫자는 거듭제곱으로 표현 가능하다고 판단합니다.

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;

bool isRepresentPower(int num) {
    if (num == 1)
        return true;
    for (int i = 2; i * i <= num; i++) {
        double val = log(num) / log(i);
        if ((val - (int)val) < 0.00000001)
            return true;
    }
    return false;
}

int main() {
    int n = 125;
    cout << (isRepresentPower(n) ? "Can be represented" : "Cannot be represented");
}

실행 결과

Can be represented

코드 설명

위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

1. 기저 조건 처리: 숫자 1은 항상 1ⁿ 형태로 표현할 수 있으므로 즉시 true를 반환합니다.

2. 밑 후보 순회: i를 2부터 시작해 i * i <= num인 동안 반복합니다. 지수가 최소 2이므로 밑은 √num을 넘을 수 없기 때문입니다.

3. 로그 계산 및 판정: log(num) / log(i)를 계산한 뒤 소수 부분을 확인하여, 그 값이 허용 오차 범위 내에 있으면 true를 반환합니다.

4. 최종 판정: 모든 후보를 검사한 후에도 조건을 만족하지 않으면 false를 반환합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(√num · log num)입니다. 밑 후보를 √num개 탐색하고, 각 후보마다 로그 연산을 수행하기 때문입니다. 공간 복잡도는 O(1)로 추가 메모리가 거의 필요하지 않습니다.