[C/C++] 10진법 -> N진법 변환

Theory

X진법 수를 X로 나누면 한 자리씩 소수점으로 이동하게 된다. 아래 예제를 보면 알 수 있다.

 

10진법        

123 / 10 = 12.3

12.3 / 10 = 1.23

 

2진법

1011 / 2 = 101.1

 

또한 어떤 수를 10진법으로 표기를 하든, 2진법으로 표기를 하든, 16진법으로 표기를 하든 결국 다 표현하는 방식만 다를 뿐, 같은 값을 가진다.

 

10진법 11이라는 숫자를 2의 배수의 합으로 표현을 해보자.

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

위와 같이 표현이 되는데, 이 때 11이라는 10진법 수를 2로 나눈 나머지는 구하면 $2^n$ 부분이 각 1씩 떨어지고 가장 작은 부분인 $ 2^0 $부분의 계수가 나오게 된다. 이 과정을 반복하면 $ 2^n $ 중에서 $n$이 가장 작은 부분이 계속 나머지로 나오게 되고 이 나머지를 역순으로 출력하면 진법 변환이 된다.

 

따라서 어떤 수를 X로 나눈 수의 나머지를 재조합하면 X진법으로 표현이 가능하다.

나눌 때는 1의 자리 수부터 사라지기 때문에 표현할 때는 거꾸로 출력하면된다.

Code

#include <stdio.h>

void F(int N, int X)
{
	if (N == 0)
		return;

	F(N / X,X);

	if (N % X >= 10)
		printf("%c", 'A' + N % X - 10); // X가 10보다 큰 경우를 처리하기 위해서
	else
		printf("%d", N % X);
}

int main()
{
	int N, X;

	scanf("%d %d", &N, &X);

	F(N, X);
}