[알고리즘] 탐색(4) - 부분집합(Subset)

 목표 

부분집합의 원소를 구할 수 있다.
부분집합의 개수를 구할 수 있다.

 

이번 부분집합에서는 위 두가지 목표에 대해 조합을 통한 구현과 bitmask를 통한 구현을 알아보겠습니다.

 

 구현 

RecursiveSubset

첫번째는 조합을 이용한 풀이인데, 조합에 대한 코드나 지식이 부족하다면 여기를 참고하세요. 부분집합은 " 멱집합(개수) = nC0 + nC1 + nC2 + ... nCr + nCr+1 ... + nCn" 와 같은 성질을 가지고 있습니다. 조합 함수에 파라미터로 r을 넘겨주면 쉽게 구할 수 있습니다.

 

void Comb(int idx, int curr, int r)
{
	if (idx == r)
	{
		for (int i = 0; i < r; ++i)
			cout << ans[i] << " ";
		cout << '\n';
		sum++;
		return;
	}
	for (int i = curr; i < 4; ++i)
	{
		ans[idx] = arr[i];
		Comb(idx + 1, i + 1, r);
	}
}

int main()
{
	for (int i = 0; i < 4; ++i)
	{
		cout << "--- 3C" << i << " ---" << '\n';
		Comb(0, 0, i);
	}

	e = clock();
	cout << "부분집합의 개수 : " << sum << '\n';
}

 

 

 

BitmaskingSubset

 

	C	B	A
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

 

위에서 비트가 켜진곳만 순서대로 조회한다면 그것이 바로 부분집합이 됩니다. 그렇다면 비트를 어떻게 켜야할지와 그 켜진 비트를 어떻게 조회를 해야할지가 관건입니다.

 

한번 비트가 켜지는 순서를 보겠습니다. 일정한 규칙이 있다는것을 발견할 수 있습니다. 10진수로 0 -> 1 -> 2 -> 3 ... -> 8  순으로 1씩 증가하고 있는것입니다. 그렇다면 마지막 수인 8은 당연히 부분집합의 합의 개수겠죠. 앞서 재귀 호출을 통해 부분집합의 개수를 일일이 세어주었었는데, 사실 모든 nCr에 대한 조합의 합은 2^n이라는 것을 " 멱집합(개수) = nC0 + nC1 + nC2 + ... nCr + nCr+1 ... + nCn"을 통해 알 수 있습니다. 결국 비트를 키는것은 10진수 0부터 2^n까지 1씩증가 시켜주면 되는 간단한 연산이었습니다.

 

그렇다면 켜진 비트를 조회하기 위해서는 어떻게 해야할까요? 비트가 켜져있는지 꺼져있는지 확인하기 위한 비트연산자, 앤드연산자를 이용하면 됩니다. 

 

 

void Subset()
{
	for (int flag = 0; flag < (1 << n); ++flag)
	{
		for (int i = 0; i < n; ++i)
			if ((1 << i) & flag)
				cout << arr[i] << " ";
		cout << '\n';
	}
}

int main()
{
	Subset();
	cout << "부분집합의 개수 : " << (1 << n) << '\n';
}

 

 

 시간복잡도 

이항계수의 성질에  성질에 따라 한 번의 함수호출에 두 번의 함수호출을 하기 때문에 시간복잡도는 O(2^n)입니다. 아래는 원소가 27개인 집합에 대한 부분집합을 구할때의 시간측정입니다. 확실히 비트마스킹을통해  구현한것이 빠른것을 확인할 수 있습니다.  (2^27 = 134,217,728) 

 

왼쪽 재귀 / 오른쪽 비트마스킹

실행 환경 :

- windows 10 WSL2 - ubuntu 18.04

- gcc 7.4.0

- cpu : i3 

- ram : 8G