비트마스킹 - 부분집합, 조합

완전 검색 - 부분집합

• 부분집합
• 조합

부분집합 Powerset

비트 연산자

연산자	연산자의 기능
&	비트 단위로 AND 연산을 한다
|	비트 단위로 OR 연산을 한다
^	비트 단위로 XOR 연산을 한다
~	단항 연산자로서 피연산자의 모든 비트를 반전시킨다
<<	피연산자의 비트 열을 왼쪽으로 이동시킨다
>>	피연산자의 비트 열을 오른쪽으로 이동시킨다

부분집합의 수

• 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 $2^n$개이다
• 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다

반복문을 이용하여 부분집합 구하기

sel = {0, 0, 0, 0}
for i in 0 to 1:
    sel[0] = i
    for j in 0 to 1:
    sel[1] = j
    for k in 0 to 1:
        sel[2] = k
        for l in 0 to 1:
            sel[3] = l
            print(sel)

비트마스킹을 이용하여 부분집합 구하기

// N: 원소의 개수
// 부분집합의 수만큼 반복 돌리기
for (int i=0; i< (1<<N); i++) {
    // i라는 부분집합에 원소 확인하기
    for (int j=0; j<N; j++) {
        if ((i&(1<<j))>0) {
            // 처리
        }
    }
}

재귀 호출을 이용하여 부분집합 구하기

// sel[]: 해당 원소 포함 여부 저장
// n: 원소의 개수, k: 현재 depth
static void powerset(int n, int k) {
    if (n==k) { //Basis Part
        print(sel);
        return;
    } // Inductive Part
    sel[k] = false; // k번 요소 X
    powerset(n, k+1); // 다음 요소 포함 여부 결정
    sel[k] = true; // k번 요소 O
    powerset(n, k+1); // 다음 요소 포함 여부 결정
}

조합 Combination

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합(combination)이라고 부른다

조합의 수식

nCr = n!/(n-r)!r!

재귀적 표현

nCr=n-1Cr-1 + n-1Cr
nCo = 1

재귀 호출을 이용한 조합 생성 알고리즘

data[] : n개의 원소를 가지고 있는 배열
sel[]: r개의 크기의 배열, 조합이 임시 저장될 배열

comb(n, r)
    IF r == 0: print_array()
    ELSE IF n < r : RETURN
    ELSE
        sel[r-1] ← data[n-1]
        comb(n-1, r-1)
        comb(n-1, r)

반복문을 이용한 조합 생성 알고리즘

// {1, 2, 3, 4} 중 원소 3개를 뽑아보자

FOR i from 1 to 2 {
    FOR j from i+1 to 3 {
        FOR k from j+1 to 4 {
            print i, j, k;
        }
    }
}

반복문 + 재귀를 이용한 조합 생성 알고리즘

data[] : n개의 원소를 가지고 있는 배열 
sel[] : r개의 크기의 배열, 조합이 임시 저장될 배열
sidx : sel 배열의 인덱스, idx : data 배열의 인덱스

comb(idx, sidx)
    IF sidx == r: print_array()
    ELSE
        FOR i from idx to N-R+sidx
            sel[sidx] ← data[i]
            comb(i+1, sidx+1)