Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 숫자를 음수 진법(negative base) 표현으로 변환하는 방법

이 튜토리얼에서는 주어진 숫자를 음수 진법(negative base) 표현으로 변환하는 프로그램을 C++로 구현하는 방법을 알아봅니다.

음수 진법이란 밑(base)이 음수인 수 체계를 말합니다. 예를 들어 밑이 -3이라면, 숫자는 (-3)의 거듭제곱들의 합으로 표현됩니다. 흥미롭게도 음수 진법에서는 별도의 부호 없이 모든 정수(양수와 음수)를 표현할 수 있다는 장점이 있습니다.

우리에게는 하나의 숫자와 해당하는 음수 진법이 주어지며, 목표는 그 숫자를 음수 진법의 동등한 표현으로 변환하는 것입니다. 단, 이 글에서는 음수 진법 값을 -2부터 -10 사이로 제한합니다.

알고리즘 접근 방식

변환 과정은 일반적인 진법 변환과 매우 유사하지만, 한 가지 중요한 차이점이 있습니다. 바로 나머지(remainder)가 음수로 나올 수 있다는 점입니다. 전체 알고리즘은 다음과 같습니다.

  1. 입력 숫자 n이 0이면 결과는 그대로 "0"입니다.
  2. n이 0이 아닌 동안, n을 음수 진법으로 나눈 나머지를 구하고 n을 같은 값으로 나눕니다.
  3. 나머지가 음수라면, 나머지에 |negBase|를 더해 양수로 보정하고 몫에는 1을 더합니다. 이렇게 하면 각 자릿수가 항상 0 이상 |negBase| 미만의 값을 갖게 됩니다.
  4. 보정된 나머지를 문자열로 변환한 뒤 결과 문자열의 앞쪽에 붙입니다.
  5. n이 0이 되면 누적된 문자열이 곧 음수 진법 표현입니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

// 정수를 문자열로 변환하는 함수
string convert_str(int n){
    string str;
    stringstream ss;
    ss << n;
    ss >> str;
    return str;
}

// n을 음수 진법(negBase) 표현으로 변환하는 함수
string convert_nb(int n, int negBase){
    // 0의 음수 진법 표현은 0
    if (n == 0)
        return "0";

    string converted = "";
    while (n != 0){
        // 음수 진법으로 나눈 나머지 계산
        int remainder = n % negBase;
        n /= negBase;

        // 나머지가 음수이면 양수로 보정
        if (remainder < 0) {
            remainder += (-negBase);
            n += 1;
        }

        // 나머지를 문자열로 변환해 결과 앞에 추가
        converted = convert_str(remainder) + converted;
    }
    return converted;
}

int main() {
    int n = 9;
    int negBase = -3;
    cout << convert_nb(n, negBase);
    return 0;
}

출력

100

코드 설명

위 예제에서는 숫자 9를 밑 -3인 진법으로 변환합니다. 결과는 100입니다. 실제로 검증해 보면 다음과 같습니다.

1×(-3)² + 0×(-3)¹ + 0×(-3)⁰ = 1×9 + 0 + 0 = 9

즉, "100"은 밑 -3에서 정확히 9를 나타냅니다.

핵심은 나머지 보정 부분입니다. C++에서 음수를 나눌 때 나머지가 음수로 나올 수 있기 때문에, 나머지가 0보다 작으면 |negBase|를 더해 양수로 만들고 몫을 1 증가시킵니다. 이는 수학적으로 (n - remainder) / negBase 관계를 유지하면서 자릿수를 유효 범위 안으로 조정하는 것과 같습니다.

시간 복잡도

루프가 반복될 때마다 n의 절댓값은 대략 |negBase|배씩 줄어들므로, 시간 복잡도는 O(log|negBase| n)입니다. 또한 각 자릿수를 문자열 앞에 추가하는 연산 때문에 최악의 경우 O(k²)(k는 자릿수)의 문자열 비용이 발생할 수 있으며, 이를 개선하려면 뒤에 추가한 후 마지막에 뒤집는 방식을 사용할 수 있습니다.

마무리

음수 진법 변환은 일반 진법 변환 알고리즘에 나머지 보정 로직만 추가하면 손쉽게 구현할 수 있습니다. 부호 비트나 '-' 기호 없이 음수까지 표현할 수 있어 컴퓨터 과학적으로도 흥미로운 주제이니, 위 코드를 직접 실행하며 다양한 입력값으로 실험해 보시기 바랍니다.