230830 완전 검색 - 부분집합

생성 일시: 2023년 8월 29일 오후 2:49

• 부분집합
• 조합

부분집합 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)