[알고리즘 이론] 완전 탐색 - 부분 집합

완전 탐색 알고리즘

1. 순열
2. 조합
3. 부분집합

📌 Power Set

• 집합에 포함된 원소들을 선택하는 것
  
  

시간복잡도

부분 집합 공식 : 원소가 n개 일 때, 2 x 2 x 2 x ... = 2^n
(각 원소에 대해 부분집합에 포함시키거나 포함시키지 않는다라는 2가지 경우를 적용)

집합의 원소가 n개 일때,
공집합을 포함한 부분집합의 수는 $2^N$개이다.
즉,$O(2^n)$의 시간 복잡도를 가짐

😱 부분 집합도 N이 커지면 시간 복잡도가 급격히 증가함으로 완전탐색을 할때는 n크기에 주의하자!

$O(2^n)$
2^20 = 104만
2^22 = 419만
2^24 = 1677만

🤔 부분집합이 조합과 다른 점

조합은 n개 중의 r개를 뽑는 것이지만,
부분 집합은 n개 중에 0(공집합) ~ n(전체 다 뽑는 경우)를 포함한다.

✔ 문제에서 공집합을 포함하는지 아닌지를 반드시 확인하자

---

반복문을 이용한 부분집합

• 원소의 개수만큼 for문을 돌기
• 하나의 원소를 뽑을까? 안 뽑을까?를 결정 - 한 개의 for문은 2번을 돌아야 한다.

public class PowerSet_loop {

	public static void main(String[] args) {

		int[] arr = new int[] {1,2,3};
		
		int[] powerSet = new int[arr.length];  // 원소를 뽑을지 안뽑을지 결정함 , 뽑는다 : 1, 안뽑는다 : 0
		
		for(int i=0;i<2;i++) {
			powerSet[0]=i;					// 첫번째 원소를 뽑을지 안뽑을지
			
			for(int j=0;j<2;j++) {
				powerSet[1]=j;				// 두번째 원소를 뽑을지 안뽑을지

				for(int k=0;k<2;k++) {
					powerSet[2]=k;			// 번번째 원소를 뽑을지 안뽑을지
					
					for(int pick = 0;pick < arr.length; pick++) {			// 1인 것은 뽑은 것임으로 출력
						if(powerSet[pick]==1) {
							System.out.print(arr[pick]+" ");
						}
					}
					System.out.println();

				}
			}
		}
	}

}

출력
// 공집합
3
2
2 3
1
1 3
1 2
1 2 3

재귀를 이용한 부분집합

• 중복 조합이 아닐때 한 depth에서 반복문을 시작하는 초기값을 변경하여 중복을 제거

바이너리 카운팅을 이용한 부분집합