큐(Queue)를 활용해 1부터 n까지의 이진수를 생성하는 흥미로운 방법

이번 글에서는 1부터 n까지의 이진수를 생성하는 아주 흥미로운 방법을 소개합니다. 핵심 아이디어는 자료구조 중 하나인 큐(Queue)를 활용하는 것입니다.

동작 방식은 다음과 같습니다. 처음에 큐에는 첫 번째 이진수인 '1'만 넣어둡니다. 그다음 큐에서 요소를 하나 꺼내(dequeue) 출력하고, 방금 꺼낸 문자열 뒤에 '0'을 붙인 값과 '1'을 붙인 값을 각각 만들어 다시 큐에 삽입(enqueue)합니다. 이 과정을 n번 반복하면 1부터 n까지의 모든 이진수가 순서대로 출력됩니다.

알고리즘

genBinaryNumbers(n)

Begin
    빈 큐(queue)를 정의한다.
    큐에 1을 삽입한다.
    while n이 0이 아니면, 반복:
        큐에서 요소를 삭제(dequeue)하여 s1에 저장한다.
        s1을 출력한다.
        s2 := s1
        s1 뒤에 '0'을 붙여 큐에 삽입한다.
        s1 뒤에 '1'을 붙여 큐에 삽입한다.
        n을 1 감소시킨다.
    done
End

C++ 구현 예제

아래는 위 알고리즘을 C++로 구현한 코드입니다. STL의 queue<string>을 사용하면 간단하게 작성할 수 있습니다.

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

void genBinaryNumbers(int n){
    queue<string> qu;
    qu.push("1");
    while(n != 0){
        string s1 = qu.front();
        qu.pop();
        cout << s1 << " ";
        string s2 = s1;
        qu.push(s1 + "0");
        qu.push(s1 + "1");
        n--;
    }
}

int main() {
    int n = 15;
    genBinaryNumbers(n);
}

실행 결과

n = 15일 때 프로그램을 실행하면 다음과 같이 1부터 15까지의 수가 이진수 형태로 순서대로 출력됩니다.

1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

동작 원리와 시간 복잡도

이 방법이 잘 작동하는 이유는 큐의 FIFO(선입선출) 특성 때문입니다. 큐에서 먼저 들어간 이진수가 먼저 나오므로, 결과적으로 숫자 크기 순서대로 이진수가 생성됩니다. 예를 들어 '1'이 처리되면 '10'과 '11'이 큐에 추가되고, 그다음 '10'이 처리되면 '100'과 '101'이 추가되는 식으로 마치 이진 트리를 너비 우선 탐색(BFS)하는 것과 같은 패턴으로 진행됩니다.

각 숫자마다 큐 연산(push/pop)이 상수 시간에 수행되므로, 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 큐에 최대 O(n)개의 문자열이 저장될 수 있으므로 O(n)입니다. 이진수 문자열의 길이를 고려하면 실제로는 O(n log n)으로 볼 수 있지만, 여전히 매우 효율적인 방법입니다.