N진법계산 알고리즘 (2진법, 8진법, 16진법)

안녕하세요👋
오늘은 알고리즘 문제를 풀다가 진법계산을 쉽게 하는방법을 찾아서 공부하였는데 좋은 방법을 찾아내어 공유하고 저도 작성하면서 복습을 하기 위해 글을 씁니다.
보통 저는 n진법으로 수를 변환할 때에는 n으로 나눈 나머지들을 stack에 넣고 다시 꺼내는 방식으로 진법수를 찾아내곤 했는데요 이를 재귀형태로 정말 쉽고 빠르게 n진법을 10진법으로 또 10진법을 n진법으로 변환하는 방법을 찾아내어 작성해 보려고 합니다

관련 문제 : https://www.acmicpc.net/problem/11576

👀처음 풀이한 코드와 공부한 코드의 비교

처음 문제풀이 코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class conversion{
private:
    int A,B;
public:
    conversion(){
        std::cin >> A >> B;
    }
    void find_sol(){
        int N,tmp;
        stack<int> st;
        std::cin >>N;
        for(int i=0;i<N;i++){
            std::cin >> tmp;
            st.push(tmp);
        }
        N=0,tmp=1;
        while(!st.empty()){
            N+=st.top()*tmp;
            st.pop();
            tmp*=A;
        }
        while(N){
            st.push(N%B);
            N/=B;
        }
        while(!st.empty()){
            std::cout << st.top() <<' ';
            st.pop();
        }
    }
    
};
int main(){
    conversion cs;
    cs.find_sol();
    return 0;
}

공부한 뒤 코드

#include <iostream>
using namespace std;
class conversion{
private:
    int A,B;
public:
    conversion(){
        std::cin >>A >>B;
    }
    void number(int n){
        if(n==0)
            return ;
        number(n/B);
        std::cout << n%B<<' ';
    }
    void find_sol(){
        int n,sol=0;
        std::cin >> n;
        for(int i=0;i<n;i++){
            int tmp;
            std::cin >> tmp;
            sol= sol*A +tmp;
        }
        number(sol);
    }

};
int main(){
    conversion cs;
    cs.find_sol();
    return 0;
}

🔎풀이방법 및 알고리즘

위 코드는 백준 11576번 문제의 코드입니다. 딱 봐도 뒤쪽의 코드가 알아보기도 쉽고 정말 편하죠 처음 볼때 이런 방법이 있다니 싶으면서 꼭 기억해 놓고 싶었습니다. 좋은 방법들을 하나하나 배워가는게 너무 좋은것 같네요

• n진법을 10진법으로 변환 처음 코드를 보면 저는 각 자리수를 앞에서부터 받으니 스택에 저장해 놓고 뒤에서부터 꺼내어 n진법의 n만큼 tmp=1 부터 곱해가며 수를 더해가면서 10진법 수를 구했습니다. 다시말해 1, n, n*n, n*n*n... 이 수를 뒷자리 수부터 하나하나 곱해서 값에 더한 것이죠
  하지만 두번째 풀이를 보면 앞에서부터 받아 sol=sol*A+tmp 로 쉽게 10진법을 구하였습니다 (A는 n진법의 n입니다) 생각해보면 ((sol*A+tmp)*A+tmp)*A+tmp 이런 방식으로 계속 나가는 것을 알수 있고풀어보면 sol*A^3+tmp*A^2+tmp*A+tmp 따라서 앞자리수부터 맨 뒷자리까지 각 자리마다 A가 자리수에 맞게 알아서 곱해지는 것을 알 수 있습니다 이렇게 간단하게 앞에서부터 찾아내어 n진법을 10진법으로 변경할 수 있습니다
  

• 10진법의 수를 n진법으로 변환 모두가 알고있듯 10진법의 수를 n으로 나눈 나머지가 뒤에서부터 n진법의 수가 됩니다 출력은 당연히 수이기 때문에 앞에서부터 출력해야 하므로 기존의 코드에서 저는
  

  while(N){
    st.push(N%B);
    N/=B;
  }
  

(B는 n진법의 n을 의미합니다) 위와같은 형태로 stack에 N%B를 하나씩 넣어두고 빼면서 앞자리수부터 출력하였습니다 하지만 두번째 코드를 보면

void number(int n){
    if(n==0)
        return ;
    number(n/B);
    std::cout << n%B<<' ';
}

위와같은 코드로 쉽게 처리하는 것을 볼 수 있는데요 stack과 방법은 유사하지만 훨신 보기 편하고 코드가 깔끔해 보입니다 n/B을 넘겨가며 재귀의 마지막까지 가서 뒤에서부터 하나씩 n%B를 출력하는 것이죠
이런 n진법 변환 스킬은 알아두면 정말 좋을 것 같아 공부한 내용도 작성하고 방법을 공유하였습니다 그럼 다음에 더 좋은 글로 찾아오도록 하겠습니다.

긴글 봐주셔서 항상 감사합니다 앞으로도 유용한 내용을 많이 공유하겠습니다 그럼 안녕 👋