n비트 이진수 생성하기: 양쪽 절반의 비트 합이 같은 모든 숫자 찾기

이 글에서는 사용자가 입력한 비트 수 n에 대해, 왼쪽 절반과 오른쪽 절반의 비트 합이 서로 같은 모든 이진수를 생성하는 방법을 알아봅니다.

예를 들어 5비트 숫자 10001을 살펴보겠습니다. 왼쪽 절반 '10'과 오른쪽 절반 '01'의 각 자릿수 합은 모두 1로 동일합니다. 바로 이런 조건을 만족하는 숫자들을 모두 찾아내는 것이 목표입니다.

알고리즘 개요

핵심 아이디어는 재귀적으로 양쪽 절반을 동시에 채워나가면서, 현재까지의 좌우 비트 합 차이(diff)를 추적하는 것입니다. 남은 비트 수로 차이를 메울 수 없는 경우에는 가지치기를 하여 탐색 범위를 줄입니다.

genAllBinEqualSumHalf(n, left, right, diff)

n: 앞으로 채워야 할 남은 비트 수
left, right: 각각 왼쪽 절반과 오른쪽 절반 문자열 (처음에는 빈 값)
diff: 왼쪽 합에서 오른쪽 합을 뺀 현재까지의 차이

Begin
    if n is 0, then
        if diff is 0, then
            print left + right
        end if
        return
    end if
    if n is 1, then
        if diff is 0, then
            print left + 0 + right
            print left + 1 + right
        end if
        return
    end if
    if 2* |diff| <= n, then
        if left is not blank, then
            genAllBinEqualSumHalf(n-2, left + 0, right + 0, diff)
            genAllBinEqualSumHalf(n-2, left + 0, right + 1, diff-1)
        end if
        genAllBinEqualSumHalf(n-2, left + 1, right + 0, diff + 1)
        genAllBinEqualSumHalf(n-2, left + 1, right + 1, diff)
    end if
End

알고리즘 단계 설명

n = 0인 경우: 모든 비트를 다 채운 상태입니다. 이때 diff가 0이라면 좌우 합이 같으므로 left와 right를 이어 붙여 출력합니다.
n = 1인 경우: 홀수 비트라 가운데 한 자리가 남습니다. diff가 0일 때만 가운데에 0 또는 1을 넣어 두 가지 결과를 출력합니다.
그 외의 경우: 한 번에 왼쪽과 오른쪽에 비트를 하나씩 추가하며 네 가지 조합(00, 01, 10, 11)을 시도합니다. 단, 01 조합은 diff를 1 줄이고, 10 조합은 diff를 1 늘립니다.
가지치기 조건: 2 × |diff| > n이면 남은 비트로는 차이를 상쇄할 수 없으므로 더 이상 탐색하지 않습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
// left와 right 문자열을 채워 나가며, di는 좌우 합의 차이를 저장
void genAllBinEqualSumHalf(int n, string left="", string right="", int di=0) {
    if (n == 0) { // 남은 비트가 없을 때
        if (di == 0) // 차이가 0이면 좌우를 연결해 출력
            cout << left + right << " ";
        return;
    }
    if (n == 1) { // 홀수 비트로 가운데 한 자리가 남은 경우
        if (di == 0) { // 차이가 0일 때만 가운데에 0 또는 1을 넣어 출력
            cout << left + "0" + right << " ";
            cout << left + "1" + right << " ";
        }
        return;
    }
    if ((2 * abs(di) <= n)) {
        if (left != ""){ // 선행 0이 붙지 않도록 처리
            genAllBinEqualSumHalf(n-2, left+"0", right+"0", di);
            // 좌우 모두 0 추가, 차이 변화 없음
            genAllBinEqualSumHalf(n-2, left+"0", right+"1", di-1);
            // 왼쪽에 0, 오른쪽에 1 추가 → 차이 1 감소
        }
        genAllBinEqualSumHalf(n-2, left+"1", right+"0", di+1); // 왼쪽에 1, 오른쪽에 0 추가 → 차이 1 증가
        genAllBinEqualSumHalf(n-2, left+"1", right+"1", di); // 좌우 모두 1 추가, 차이 변화 없음
    }
}
main() {
    int n = 5;
    genAllBinEqualSumHalf(n);
}

실행 결과

정리

이 알고리즘은 백트래킹 기법을 활용해 좌우 대칭 위치에 비트를 쌍으로 추가하면서 불필요한 탐색을 조기에 차단합니다. 덕분에 전체 2ⁿ개의 이진수를 일일이 검사하는 브루트포스 방식보다 훨씬 효율적으로 조건을 만족하는 숫자들을 찾아낼 수 있습니다.