C++ 진법 변환 기법으로 숫자가 k의 거듭제곱인지 확인하는 방법

이 글에서는 하나의 숫자 n과 밑 값 k가 주어졌을 때, n이 k의 거듭제곱인지 판별하는 프로그램을 살펴봅니다. 특히 진법 변환(base changing) 기법을 활용해 문제를 해결하는 것이 핵심 포인트입니다.

예를 들어 숫자가 27이고 k = 3이라고 가정해 보겠습니다. 27을 3진수로 변환하면 1000이 됩니다. 이처럼 진법을 변환한 결과에서 숫자 1이 딱 한 번만 등장하고 나머지 자릿수가 모두 0이라면, 그 수는 k의 거듭제곱이라고 판단할 수 있습니다.

해결 절차

• flag := false로 초기화합니다.
• number > 0인 동안 아래 3~6단계를 반복합니다.
• digit := number mod k 로 현재 자릿수를 구합니다.
• digit > 1이면 false를 반환합니다. (자릿수에 0 또는 1 외의 값이 있으면 거듭제곱이 아닙니다.)
• digit == 1일 때, flag가 이미 true라면 false를 반환하고, 그렇지 않다면 flag := true로 설정합니다.
• number := number / k 로 값을 갱신합니다.
• 반복이 정상적으로 끝나면 true를 반환합니다.

예제 코드

#include <iostream>
#include <cmath>
using namespace std;
bool isPowerOfK(int num, int k) {
    bool flag = false;
    while (num > 0) {
        int digit = num % k; // k진법에서 현재 자릿수 구하기
        if (digit > 1) // 자릿수가 0 또는 1이 아니면 k의 거듭제곱이 아님
        return false;
        if (digit == 1) {
            if (flag)
               return false;
            flag = true;
        }
        num /= k;
    }
    return true;
}
int main() {
    int number = 27, K = 3;
    if(isPowerOfK(number, K)){
        cout << number << " is power of " << K;
    } else {
        cout << number << " is not power of " << K;
    }
}

실행 결과

27 is power of 3

동작 원리와 복잡도

이 알고리즘은 주어진 수를 k진법으로 한 자릿수씩 분해하면서 검사합니다. k의 거듭제곱을 k진수로 표현하면 항상 '1 뒤에 0이 여러 개 붙는 형태'가 되므로, 자릿수 중에 2 이상의 값이 존재하거나 1이 두 번 이상 나타나면 즉시 false를 반환합니다.

시간 복잡도는 숫자를 k로 계속 나누기 때문에 O(log_k n)이며, 추가 메모리 없이 플래그 변수 하나만 사용하므로 공간 복잡도는 O(1)입니다. 참고로 n = 1인 경우에는 반복문이 실행되지 않고 true를 반환하는데, 이는 1 = k⁰이므로 올바른 결과입니다.