10진수를 2진수로 변환하는 재귀 알고리즘 완벽 가이드

10진수는 얼마든지 2진수 형태로 변환할 수 있습니다. 10진수를 2진수로 바꾸려면 해당 수가 0 또는 1이 될 때까지 2로 계속 나누면 됩니다. 이때 각 단계에서 발생하는 나머지(remainder)를 별도로 저장한 후, 역순으로 나열하면 원하는 2진수 값을 얻을 수 있습니다.

이 글에서 소개하는 알고리즘은 재귀(recursion) 방식을 사용합니다. 재귀를 활용하면 스택 자료구조를 직접 구현하지 않고도 문제를 손쉽게 해결할 수 있습니다. 함수가 재귀적으로 호출될 때 내부적으로 시스템 스택이 사용되기 때문에, 우리는 그 내부 스택을 그대로 활용해 작업을 처리하면 됩니다.

입력과 출력

입력:
10진수 56
출력:
2진수 값: 111000

알고리즘

decToBin(decimal)

입력: 10진수 숫자

출력: 2진수 문자열

시작
    만약 decimal이 0 또는 1이라면
        decimal을 2진수 문자열에 삽입
        반환
    decToBin(decimal / 2) 호출
    (decimal mod 2) 값을 2진수 문자열에 삽입
끝

동작 원리

재귀 호출은 먼저 수를 2로 나눈 몫에 대해 다시 자기 자신을 호출합니다. 가장 안쪽 재귀(수가 0 또는 1이 되는 시점)부터 반환되면서, 각 단계의 나머지가 역순으로 출력됩니다. 결과적으로 최상위 비트(MSB)부터 하위 비트(LSB)까지 올바른 순서의 2진수가 완성됩니다.

C++ 구현 예제

#include<iostream>
using namespace std;

void decToBin(int dec) {
    if(dec == 1 || dec == 0) {
        cout << dec;          // 0 또는 1을 그대로 출력
        return;
    }

    decToBin(dec/2);          // 수를 2로 나누어 다시 재귀 호출
    cout << dec % 2;          // 반환된 후 나머지를 역순으로 출력
}

main() {
    int dec;
    cout<<"Enter decimal number: "; cin >> dec;
    cout << "Binary Equivalent: "; decToBin(dec);
}

실행 결과

Enter decimal number: 56
Binary Equivalent: 111000

예제에서 입력한 56은 2진수로 111000임을 확인할 수 있습니다. 이처럼 재귀 함수를 사용하면 반복문이나 명시적인 스택 없이도 간결하고 직관적으로 10진수→2진수 변환을 구현할 수 있습니다.