멱집합이란?
특정 집합이 가질 수 있는 모든 부분집합을 멱집합이라고 한다.
멱집합의 모든 경우의 수는 2^n 이다
- 원소를 포함하던가, 포함하지 않던가 두가지 경우가 n 개 있기때문
{a, b, c, d, e, f} 의 모든 부분집합을 나열하려면
- a를 제외한 {b,c,d,e,f} 의 모든 부분집합들을 나열하고
- {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.
{b, c, d, e, f} 의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면
- {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고
- {c,d,e,f}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열한다.
앞선 경우들을 보면 {a} → {a,b} 와 같이 집합이 늘어나는 것을 볼 수 있다. 이 같은 경우와 특정 집합의 부분집합을 구하기 위해선 인자를 두 개 받도록 함수를 설계해야 한다.
멱집합은 재귀 알고리즘을 사용해서 간명하게 나타낼 수 있다.
P는 제외시키려는 원소의 집합이며 S는 구하려는 멱집합을 나타낸다.
base case는 S가 공집합일 때이고 공집합의 부분집합은 공집합 뿐이다. 여기에 P를 합집합한다는 것은 결국 P만 출력해서 보여주면 된다는 것이다.
공집합이 아니라면
- t를 포함하지 않는 경우
- t를 포함하는 경우
각각을 처리하도록 재귀함수를 호출한다.
맨 처음 powerset 함수를 호출할 땐 powerset(공집합, data) 와 같은 형태로 호출하면 된다.
인덱스를 사용하면 위에서 표현한 수도코드를 인자 하나만 받도록 더욱 쉽게 표현할 수 있다.
이를 boolean으로 표현할 수 있는데, 해당 인덱스의 원소가 참이면 집합에 포함됬다고 보는 식이다.
코드로 옮기면 다음과 같다.
k 값이 증가되며 data의 길이와 같아질 때 == s가 공집합이 됬을 때
루프를 돌며 true로 표시된 것들을 모두 출력한다 == p집합을 모두 표시한다
includes[k] = true || false 는 해당 원소를 포함시키냐, 안시키느냐를 나타낸다.
상태공간트리를 보고 나면 코드가 더 쉽게 이해된다. 상태공간트리란 모든 멱집합을 구하는 과정을 트리로 시각화 한 것이다.
상태공간트리란?
- 해를 찾기 우해 탐색할 필요가 있는 모든 후보들을 포함하는 트리
- 트리의 모든 노드들을 방문하면 해를 찾을 수 있다.
- 루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술한다.
상태공간트리로 코드를 보면 다음과 같다.
k값은 현재 트리상의 레벨 및 어떤 노드를 선택하겠다는 것을 뜻하며 0 ~ k-1 사이의 값은 이전 트리 레벨에서 어떤 노드를 선택했는지를 뜻한다.
여기까지가 멱집합에 대한 정리이다.
출처
권오흠 교수님의 알고리즘 강의 링크
