진법 변환

진법이란?

우리가 쓰는 10진법은 0~9 열 개의 숫자로 수를 표현합니다. N진법은 \(N\)개의
숫자만으로 수를 나타내는 방식입니다. 2진법(0,1), 8진법, 16진법(0_9,AF)이 자주
쓰입니다.

1. 자릿값의 의미

10진수 \(342\)는 \(3 \times 10^2 + 4 \times 10^1 + 2 \times 10^0\)입니다. 진법이 바뀌면
밑(base) 만 바뀝니다. 2진수 \(1011\)은:

$$ 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 11 $$

즉 "각 자리 숫자 × 밑의 거듭제곱"의 합이 10진수 값입니다.

2. N진수 → 10진수 (읽기)

왼쪽부터 자리마다 밑을 곱해 누적하면 됩니다.

1011 (2진) 을 10진으로:
0
0*2 + 1 = 1
1*2 + 0 = 2
2*2 + 1 = 5
5*2 + 1 = 11

"지금까지 값 × 밑 + 새 자리"를 반복하는 호너(Horner) 방식이 깔끔합니다.

3. 10진수 → N진수 (쓰기)

밑으로 계속 나누면서 나머지를 거꾸로 읽습니다.

11을 2진수로:
11 / 2 = 5 ... 1
 5 / 2 = 2 ... 1
 2 / 2 = 1 ... 0
 1 / 2 = 0 ... 1
나머지를 아래에서 위로: 1011

나머지가 거꾸로 나온다는 게 핵심 포인트입니다.

4. 10을 넘는 자리 (16진법 등)

16진법은 한 자리에 0~15가 들어가므로, 10~15를 A~F로 표기합니다.

숫자 ↔ 문자 변환은 아스키 코드를 씁니다('A' + (값-10)).

복잡도

변환은 자릿수에 비례합니다. \(N\)진법으로 표현한 자릿수는 약 \(\log_N(\text{값})\)이라
사실상 \(O(\log)\)로 매우 빠릅니다.

정리

• N진수 값 = \(\sum (\text{자리 숫자}) \times N^{\text{위치}}\).
• N진 → 10진: "값 × 밑 + 새 자리" 반복.
• 10진 → N진: 밑으로 나눈 나머지를 거꾸로.
• 10 이상 자리는 A~F 등 문자로(아스키 활용).

진법 변환 구현 레퍼런스

두 방향 변환을 직접 구현하고, 16진법 같은 문자 자리 처리와 함정을 코드로 정리합니다.

1. N진수 → 10진수

string s; int base;
cin >> s >> base;
long long value = 0;
for (char c : s) {
    int digit = (c <= '9') ? c - '0' : c - 'A' + 10;  // 0-9 또는 A-F
    value = value * base + digit;                      // 호너 방식
}
cout << value << '\n';

s = input()
base = int(input())
print(int(s, base))     # 파이썬은 int(문자열, 진법)으로 한 방에

C++의 value = value * base + digit이 핵심 누적식입니다. 문자 자리는 아스키로
숫자화합니다.

2. 10진수 → N진수

long long n; int base;
cin >> n >> base;
if (n == 0) { cout << 0 << '\n'; return 0; }   // 0은 특수 처리
string result = "";
while (n > 0) {
    int d = n % base;
    char c = (d < 10) ? ('0' + d) : ('A' + d - 10);
    result += c;          // 나머지를 뒤에 붙이고
    n /= base;
}
reverse(result.begin(), result.end());   // 거꾸로 뒤집어야 함!
cout << result << '\n';

def to_base(n, base):
    if n == 0:
        return "0"
    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    out = ""
    while n > 0:
        out = digits[n % base] + out   # 앞에 붙이면 뒤집을 필요 없음
        n //= base
    return out

print(to_base(int(input()), int(input())))

나머지를 뒤에 붙였다면 마지막에 뒤집어야 합니다. 앞에 붙이면 뒤집기 불필요.

3. 진법 사이 직접 변환

A진수 → B진수는 "A진 → 10진 → B진"으로 두 단계를 잇습니다.

n = int(input(), 5)        # 5진수를 10진수로
# 다시 to_base(n, 3) 으로 3진수 출력

4. 함정과 패턴 인식

• 거꾸로 출력 — 나머지를 모은 뒤 뒤집기를 빠뜨려 순서가 반대로.
• 0 처리 — 입력이 0이면 while이 안 돌아 빈 문자열. 따로 "0" 출력.
• 문자 자리 — 10 이상은 A~F. 'A' + d - 10 공식.
• 오버플로 — 누적 값이 클 수 있으면 long long.

문제에 "2/8/16진수로 변환", "X진법으로 나타내라", "이진수의 1의 개수" 같은
말이 보이면 진법 변환입니다.

정리

진법 변환은 (1) N진→10진은 "값×밑+자리" 누적, (2) 10진→N진은 나머지를 모아
뒤집기, (3) 10 이상 자리는 A~F 문자, (4) 0과 오버플로 처리 — 이 네 가지만
챙기면 됩니다. 파이썬은 int(s, base)로 한쪽이 공짜입니다.