스택(Stack)을 활용한 10진수 → 2진수 변환 C++ 프로그램

이번 글에서는 스택(Stack) 자료구조를 활용하여 10진수를 2진수로 변환하는 C++ 프로그램을 살펴봅니다.

10진수를 2진수로 변환하는 기본 원리는 숫자를 2로 계속 나누면서 나머지(remainder)를 구하는 것입니다. 이때 나머지는 구해진 순서의 역순, 즉 마지막에 구한 값부터 처음 값까지 거꾸로 읽어야 최종 2진수가 됩니다. 스택은 LIFO(Last In First Out, 후입선출) 구조이므로, 나머지를 차례대로 저장했다가 꺼내면 자동으로 역순으로 출력되기 때문에 이 문제에 가장 적합한 자료구조입니다.

입력: 10진수 13
출력: 2진수 1101

알고리즘

변환 과정은 다음과 같은 단계로 진행됩니다.

Step 1: 10진수를 입력받는다.
Step 2: 숫자가 0보다 클 동안 반복한다.
  Step 2.1: 숫자를 2로 나눈 나머지를 스택에 push 한다.
  Step 2.2: 숫자를 number / 2 로 갱신한다.
Step 3: 스택이 빌 때까지 pop 하며 출력하면 2진수가 완성된다.

동작 원리 예시 (13 → 1101)

10진수 13을 변환하는 과정을 단계별로 보면 다음과 같습니다.

• 13 ÷ 2 = 몫 6, 나머지 1 → 스택에 push
• 6 ÷ 2 = 몫 3, 나머지 0 → 스택에 push
• 3 ÷ 2 = 몫 1, 나머지 1 → 스택에 push
• 1 ÷ 2 = 몫 0, 나머지 1 → 스택에 push

스택에는 아래쪽부터 [1, 0, 1, 1] 순서로 쌓여 있으며, pop 하면 1 → 1 → 0 → 1, 즉 1101이 출력됩니다.

예제 코드

#include <iostream>
#include <stack>
using namespace std;

void dec_to_bin(int number) {
    stack<int> stk;
    while (number > 0) {
        int rem = number % 2;   // 2로 나눈 나머지를 구함
        number = number / 2;    // 몫으로 숫자를 갱신
        stk.push(rem);          // 나머지를 스택에 저장
    }
    while (!stk.empty()) {      // 스택이 빌 때까지 pop 하며 출력
        cout << stk.top();
        stk.pop();
    }
}

int main() {
    int num;
    cout << "숫자를 입력하세요: ";
    cin >> num;
    dec_to_bin(num);
    return 0;
}

실행 결과

숫자를 입력하세요: 18
10010

복잡도 분석

n을 2로 나눌 때마다 자릿수가 하나씩 줄어들므로, 반복 횟수는 n의 비트 길이에 비례합니다.

• 시간 복잡도: O(log₂ n)
• 공간 복잡도: O(log₂ n) — 나머지를 저장하기 위한 스택 공간

이처럼 스택을 사용하면 나머지를 역순으로 조립하는 과정을 별도의 배열 인덱스 관리 없이 깔끔하게 처리할 수 있습니다.