Algorithms

2.3 Base Conversion

개념

BB진법은 한 자리에 00부터 B−1B-1까지의 값을 사용합니다. 오른쪽부터 자릿값이 B0,B1,B2B^0,B^1,B^2 순서로 커집니다. 1010 이상의 자릿값에는 A, B 등의 문자를 사용합니다.

예를 들어 22진수 1011은 각 자릿값을 더한 1×23+0×22+1×21+1×20=111\times2^3+0\times2^2+1\times2^1+1\times2^0=11을 뜻합니다. 진법 변환은 같은 수의 자릿값 표현을 바꾸는 과정입니다.

다른 진법에서 10진법으로

왼쪽부터 현재 값에 밑을 곱하고 다음 자릿값을 더합니다. 22진수 1011은 1→2→5→111\to2\to5\to11 순서로 누적되어 1010진수 1111이 됩니다.

왼쪽부터 읽으며 진법을 곱하는 이유는 기존 숫자들의 자리가 한 칸씩 올라가기 때문입니다. 22진수 10까지 읽은 값은 22이고, 다음 자리 1을 붙이면 2×2+1=52\times2+1=5가 됩니다. 한 자리 더 1을 붙이면 5×2+1=115\times2+1=11입니다.

10진법에서 다른 진법으로

수를 밑으로 나누고 나머지를 기록합니다. 나머지는 가장 낮은 자리부터 얻어지므로 역순으로 읽습니다. 1111을 22로 반복해서 나눈 나머지는 1,1,0,11,1,0,1이며 결과는 1011입니다. 값이 00이면 표현도 0입니다.

1010진수 2626은 22진수 11010, 88진수 32, 1616진수 1A입니다. 서로 다른 두 진법 사이의 변환은 값을 누적한 뒤 새 진법으로 표현합니다.

N=Bq+rN=Bq+r에서 나머지 rr은 00부터 B−1B-1까지이므로 BB진법의 마지막 자리입니다. 몫 qq는 그 마지막 자리를 제거한 값입니다. 이 나눗셈을 반복하면 낮은 자리부터 하나씩 구할 수 있습니다.

나누기 전 값22로 나눈 몫나머지
11115511
552211
221100
110011

나머지는 마지막 자리부터 나왔으므로 표의 아래에서 위로 읽은 1011이 결과입니다.

복잡도

입력 자릿수를 LL, 출력 자릿수를 KK라고 합니다.

연산시간복잡도공간복잡도
진법 변환O(L+K)O(L+K)출력 저장 O(K)O(K)

예제

문제

소문자로 표현된 2626진수를 1010진수로 변환하고, 주어진 1010진수를 소문자로 표현된 2626진수로 변환하여라. a는 00, b는 11, …\ldots, z는 2525를 나타낸다.

입력

첫째 줄에 소문자로 이루어진 2626진수 SS가 주어진다. 길이는 11 이상 33 이하이며, 나타내는 값은 00 이상 9 9999\,999 이하이다.

둘째 줄에 1010진수 NN이 주어진다. 0≤N≤9 9990\le N\le9\,999이다.

출력

첫째 줄에 SS를 1010진수로 변환한 값을 출력한다. 둘째 줄에 NN을 소문자로 표현된 2626진수로 변환한 결과를 출력한다. 값이 00이면 a를 출력하고, 그 외에는 맨 앞에 a를 붙이지 않는다.

예제 입력

bca
28

예제 출력

728
bc

예제 코드

C++20

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    string s, ans;
    int n, x, r;

    cin >> s >> n;
    x = 0;

    // 왼쪽부터 26진수의 자릿값을 누적함
    for (char c : s) {
        x = x * 26 + (c - 'a');
    }
    cout << x << '\n';

    // 낮은 자리부터 구한 뒤 순서를 뒤집음
    if (n == 0) ans = "a";
    while (n > 0) {
        r = n % 26;
        ans += char('a' + r);
        n /= 26;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
}