챕터4-3. 수학 | 진법변환(Base Conversion)

진법변환(Base Conversion)

# 세 줄 요약
- A진법을 B진법으로 바꾸고 싶다면 "A진법 -> 10진법 -> B진법" 을 거치면 된다.(A, B는 10진법이 아님)
- "A진법 -> 10진법", "10진법 -> B진법" 각각의 변환 방법은 아래와 같다.

- 입력이 0이 들어올 때 출력이 0으로 되도록 처리해주는 것을 깜빡하지 말자.

 

# 개념

n진법이란 각 자리가 0 ~ n-1의 수로 표현되는 것을 말함

@ A진법의 수 -> 10진법의 수 변환 방법
- 방법1) 2진법을 10진법으로 바꾸는 방법을 생각하면 됨.
              2진법 101은 10진법으로 1*2^2 + 0*2^1 + 1*2^0 = 5
              ex) 3진법의 수 102를 10진법의 수로 변환하는 예시
               1*3^2 + 0*3^1 + 1*3^0 = 11

- 방법2) 처음 접하는 방법인데 제곱해주는 과정이 없어서 기존 방법보다 편함.

             A진법의 수 N이라면 ans = 0로 시작하여
             각 자리에 대해서 ans = (ans * A) + N[i];  // 이전결과를 이용해서 곱셈을 하지, 위의 방법1처럼 합산을 하진 않는다.
              ex) 3진법의 수 102를 10진법의 수로 변환하는 예시
              ans = 0 
              ans = ans*3 + 1 = 1
              ans = ans*3 + 0 = 3
              ans = ans*3 + 2 = 11  // 최종결과              

 

@ 10진법의 수 -> B진법의 수 변환 방법
- 10진법을 2진법으로 바꾸는 방법을 생각하면 된다.
   10진법의 수가 0이 될 때까지 B의 값으로 나눠주며 나머지를 계속 구하고, 나온 나머지들을 아래서부터 적어주면 된다.
- ex) 10진법의 수 11을 3진법의 수로 변환하는 예시
         11 / 3 = 3...2,    
         3 / 3 = 1...0
         1 / 3 = 0...1       -> 여기서부터 적어주면 됨 즉, 10진수 11은 3진법으로 102이다.

- 10이상의 나머지가 나오는 경우에 A ~ Z로 치환한다면 string, reverse를 이용한 방식을 사용해도 되지만
   치환해주는 과정 없이 그냥 출력해주는 방식이라면 reverse를 사용하면 안되므로 벡터를 이용하던가 해라.

 

@ (예외) 2진법의 수 -> 2^n 진법의 수(n>2, 즉, 4, 8, 16, 32, ... ) 

- 2진수를 뒤에서부터 n개씩 끊어서 10진법으로 각각을 변환시켜준 뒤 이어붙이면 된다.
   (n개씩 끊었기 때문에 알아서 각 진법에 맞게 변환됨)

@ (예외) 2^n 진법의 수(n>2) -> 2진법의 수

- 각 자리의 수를 n자리의 2진수로 변환하여 이어붙이면 된다.

위 개념을 적용한 문제풀이

# 진법 변환2 문제
- https://www.acmicpc.net/problem/11005
- 10진법의 수 N을 B진법으로 바꿔서 출력하는 문제

 

# 진법 변환 문제

- https://www.acmicpc.net/problem/2745
- B진법의 수 N을 10진법으로 바꿔서 출력하는 문제
- 이미 알고있는 방법이 아닌 변환 방법2를 이용하여 계산해보자. 그것이 실제 더 편리하다.

 

# 2진수 -> 8진수 변환 문제
- https://www.acmicpc.net/problem/1373

- 2진 -> 10진 -> 8진 으로 변환할 필요가 없다. 바로 2진 -> 8진으로 가능.
- 2진수는 한자리를 0~1로만 표현하듯이 8진수는 한자리를 0~7로 표현한다. 즉 3비트가 필요함 따라서 2진수를 3자리씩 묶어주면 8진수가 됨.
ex ) 2진수 101 110 011
       101 = 5
       110 = 6
       011 = 3
      따라서 2진수 101110011는 8진수로 563이 됨
- 16진수를 2진수를 4개씩, 32진수는 2진수를 5개씩 묶으면 된다. 2^k진수일때 2진수를 k비트씩 묶어주면 되는것이다.

 

# 8진수 -> 2진수 변환 문제
- https://www.acmicpc.net/problem/1212
- 각 자리를 2진수로 변환해주고 맨 앞자리의 수가 아니라면 0을 이용해서 3자리로 맞춰줘야함.

# 10진수 N -> (-2)진수 변환 문제
- https://www.acmicpc.net/problem/2089
- 특이케이스 문제
- 연산의 종류에는 "양수/2, 음수/2" 두 가지의 경우가 존재한다 그런데 나머지만 보면 3가지의 경우로 나눌 수 있다.
   (2로 나눈 나머지가 0인 경우), (2로 나눈 나머지가 0이 아닌데 n이 양수인 경우, n이 음수인경우)
- 양수/-2의 예시
   ex) 6/2 = 3...0,       -------- case 1
          7/2 = 3...1        -------- case 2
- 음수/-2의 예시
   ex) -6/2 = -3...0,    -------- case 1
          -7/2 = -3...-1    -------- case 3
- n이 2로 나누어 떨어지면 나머지는 0, n = -(n/2) 으로 처리하고
   n이 2로 나누어 떨어지지 않으면 나머지는 1, 양수인 경우와 음수인 경우를 나누어 처리한다.
   양수인 경우는 n = -(n/2), 음수인 경우는 n = (-n+1) / 2
   이를 0이 될때까지 수행한 뒤 reverser를 해주면 된다.

# A진법 수를 B진법으로 바꾸는 문제
- https://www.acmicpc.net/problem/11576
- A진법을 B진법으로 바꾸려면 A진법 -> 10진법 -> B진법 의 과정을 거치면 된다.
- 여기서는 10진법 -> B진법 할 때 string을 사용하면 안되는게 
   reverse를 해주면 두 자리의 수의 경우일 때 문제가 되버리기 때문이다.