이 글에서는 이진 계수법(Binary Counting Method)을 활용하여 집합의 모든 부분 집합(멱집합)을 생성하는 C++ 프로그램을 소개합니다. 이 방법은 각 원소의 포함 여부를 이진수 비트로 표현하는 아이디어를 기반으로 하며, n개의 원소가 있는 집합은 총 2ⁿ개의 부분 집합을 가질 수 있습니다.
동작 원리
이진 계수법의 핵심 아이디어는 다음과 같습니다. 집합의 각 원소에 대해 해당 원소가 부분 집합에 포함되면 '1', 포함되지 않으면 '0'으로 표시하는 이진 문자열을 사용합니다. 예를 들어, 이진수 '1010'은 첫 번째와 세 번째 원소만 포함된 부분 집합을 의미합니다.
0부터 2ⁿ-1까지의 모든 정수를 이진수로 나타내면, 그것이 곧 가능한 모든 부분 집합의 조합과 일대일로 대응됩니다.
알고리즘 단계
시작
배열의 원소들을 입력받는다.
함수 BinaryCounting():
r = pow(2, n) 계산 // n은 원소의 개수
0부터 r-1까지의 이진수를 생성한다.
각 n자리 이진 문자열마다 solution() 함수를 호출한다.
끝C++ 구현 코드
#include<iostream>
#include<math.h>
using namespace std;
void solution(char code[], int a[], int n) // 결과 출력 함수
{
int i;
cout<<"\t { ";
for(i = 0; i < n; i++) {
if(code[i] == '1')
cout<<a[i]<<" ";
}
cout<<"}\n";
}
int BinaryCounting(int a[], int n) {
int r, i, l;
char bin[] = "00000";
r = pow(2, n);
// 0부터 r-1까지의 이진수를 생성
for(i = 0; i < r; i++) {
solution(bin, a, n);
l = n - 1;
h:
if(bin[l] == '0')
bin[l] = '1';
else {
bin[l] = '0';
l--;
goto h;
}
}
}
int main() {
int i, n;
cout<<"\nEnter the number of elements: ";
cin>>n;
int a[n];
cout<<"\n";
for(i = 0; i < n; i++) {
cout<<"Enter "<<i+1<<" element: ";
cin>>a[i];
}
cout<<"\nThe subset in the binary counting method: \n";
BinaryCounting(a, n);
return 0;
}코드 설명
- solution(): 현재 이진 문자열(bin)을 검사하여 값이 '1'인 위치의 배열 원소만 출력합니다. 즉, 해당 비트 위치의 원소가 부분 집합에 포함된 경우입니다.
- BinaryCounting(): 전체 부분 집합의 개수인 2ⁿ을 계산한 뒤, 이진 문자열을 하나씩 증가시키며 매번 solution()을 호출합니다. 내부의 레이블(h)과 goto 문은 이진수 자리올림(carry) 로직을 구현한 것으로, 오른쪽 비트부터 검사하여 '0'이면 '1'로 바꾸고, '1'이면 '0'으로 바꾼 후 왼쪽 자리로 이동합니다.
실행 결과
Enter the number of elements: 4
Enter 1 element: 4
Enter 2 element: 3
Enter 3 element: 2
Enter 4 element: 1
The subset in the binary counting method:
{ }
{ 1 }
{ 2 }
{ 2 1 }
{ 3 }
{ 3 1 }
{ 3 2 }
{ 3 2 1 }
{ 4 }
{ 4 1 }
{ 4 2 }
{ 4 2 1 }
{ 4 3 }
{ 4 3 1 }
{ 4 3 2 }
{ 4 3 2 1 }위 실행 결과에서 볼 수 있듯이, 4개의 원소로 이루어진 집합은 공집합({ })부터 전체 집합({ 4 3 2 1 })까지 총 16개(2⁴)의 부분 집합을 생성합니다. 이처럼 이진 계수법은 시간 복잡도 O(n × 2ⁿ)으로 모든 부분 집합을 체계적으로 열거할 수 있는 효율적이고 직관적인 방법입니다.