C++로 정렬된 순서대로 n비트(1 ≤ n ≤ k)가 설정된 k비트 숫자의 모든 조합 찾기

문제 개요

하나의 수 k가 주어졌을 때, 설정된 비트(set bit)의 개수가 n개(1 ≤ n ≤ k)인 k비트 숫자의 모든 조합을 찾는 것이 목표입니다. 결과는 설정 비트가 1개인 숫자들부터 먼저 출력하고, 이어서 2개인 숫자들, 마지막으로 모든 비트가 설정된 숫자까지 차례로 출력합니다. 설정 비트의 개수가 서로 같다면 더 작은 숫자가 앞에 오도록 정렬합니다.

예를 들어 k = 3일 때 결과는 [001, 010, 100, 011, 101, 110, 111] 순서가 됩니다.

풀이 접근: 동적 계획법

이 문제는 동적 계획법(Dynamic Programming)으로 깔끔하게 해결할 수 있습니다. 길이가 k이고 1이 n개 포함된 조합은 다음 두 부분으로 분해할 수 있습니다.

• '0' 접두사 추가: 길이가 k − 1이고 1이 n개인 모든 조합 앞에 0을 붙입니다.
• '1' 접두사 추가: 길이가 k − 1이고 1이 n − 1개인 모든 조합 앞에 1을 붙입니다.

이 규칙을 비트 길이 1부터 k까지 반복적으로 적용하면, 2차원 테이블 table[bit][n]에 "설정 비트가 n개인 bit비트 문자열"이 자연스럽게 정렬된 순서로 쌓이게 됩니다.

C++ 구현

#include<iostream>
#include<vector>
#define K 16
using namespace std;
vector<string> table[K][K];
void getCombinations(int k) {
    string str = "";
    for (int bit = 0; bit <= k; bit++) {
        table[bit][0].push_back(str);
        str = str + "0";
    }
    for (int bit = 1; bit <= k; bit++) {
        for (int n = 1; n <= bit; n++) {
            for (string str : table[bit - 1][n])
                table[bit][n].push_back("0" + str);
            for (string str : table[bit - 1][n - 1])
                table[bit][n].push_back("1" + str);
        }
    }
    for (int n = 1; n <= k; n++) {
        for (string str : table[k][n])
            cout << str << " ";
        cout << endl;
    }
}
int main() {
    int k = 4;
    getCombinations(k);
}

실행 결과

k = 4로 프로그램을 실행하면 아래와 같이 설정 비트 개수별로 묶인 숫자들이 출력됩니다.

0001 0010 0100 1000
0011 0101 0110 1001 1010 1100
0111 1011 1101 1110
1111

복잡도 분석

생성되는 문자열의 총 개수는 2^k − 1개이고, 각 문자열의 길이는 k이므로 시간 복잡도와 공간 복잡도는 모두 O(2^k × k)입니다. 따라서 k 값이 커지면 조합의 수가 기하급수적으로 증가한다는 점을 유의해야 합니다.