[Python] 진수 변환

코딩테스트 문제들을 풀다보면 진수 변환을 하는 문제가 자주 등장한다. 오늘은 진수 변환을 하는 방법 2가지를 소개한다.

10 진수 -> n 진수

10진수를 n 진수로 바꾸는 것은 학생 때 배웠던 2진법 변환방법을 코드로 구현한 것과 같다.

바꾸고 싶은 수를 n으로 나누고 나머지와 몫을 확인한다. 몫이 0이 되면 나머지들을 역순으로 문자열에 추가한다.

1. 반복문 사용

def convert_iter(num, base):
    power = 0
    tmp = ''
    while num:
        tmp = str(num%base) + tmp
        num //= base
    return tmp

이 방법으로는 10진수까지의 변환만 가능하다.

2. 재귀함수 사용

import string

def convert_recur(num, base):
    number = string.digits + string.ascii_uppercase
    q, r = divmod(num, base)
    return convert_recur(q, base) + number[r] if q else number[r]

string.digits = '0123456789'이고 string.ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'이다. 둘 다 문자열이고 따라서 우리가 구하고자 하는 수가 x일 때 number[x] = 'x'로 11 진수 이상의 진법도 표현 가능하다.

n 진수 -> 10진수

n 진수를 10진수로 바꾸는 방법은 굉장히 간단하다. 내장 int함수에 구현되어 있다. 사용 방법은 다음과 같다.

base_2 = '10011010010'
base_8 = '2322'
base_16 = '4d2'

print(int(base_2, 2))    # 1234
print(int(base_8, 8))    # 1234
print(int(base-16, 16)) # 1234

int(number_string, base)로 나타낼 수 있다. 첫 번째 인자는 무조건 문자열이어야 하고 base가 달라지면 값도 달라진다. 그리고 만약 문자열이 '1234'인데 2진법으로 나타낸 수라고 하는 것은 에러가 발생한다.

이외의 방법들

내장 함수 사용

2진법, 8진법, 16진법은 파이썬 내장 함수로 진수 변환이 가능하다.

h = hex(1234)
o = oct(1234)
b = bin(1234)

print(h)    # '0x4d2'
print(o)    # '0o2322'
print(b)    # '0b10011010010'
# 다시 10진수로 변환하기
print(int(h, 16)) # 1234
print(int(o, 8)) # 1234
print(int(b, 2)) # 1234

변환 시간 측정

import time

start = time.time()
for _ in range(100000):
    bin(1234)
print("내장 함수 시간 : {}".format(time.time()-start))

start = time.time()
for _ in range(100000):
    convert_iter(1234, 2)
print("반복 함수 시간 : {}".format(time.time()-start))

start = time.time()
for _ in range(100000):
    convert_recur(1234, 2)
print("재귀 함수 시간 : {}".format(time.time()-start))

확실히 파이썬은 내장 함수를 안다면 무조건 내장함수를 쓰는 것이 효율적이다. 재귀 함수가 오히려 더 효율이 좋을 거라 생각했는데 반복 함수를 사용할 때가 더 효율이 좋다. 시간 복잡도의 차이보다 함수 호출에서 시간이 조금 더 걸려서인 듯 하다.