부분집합

부분집합을 구하는 방법 중 재귀함수와 비트연산자를 이용하는 방법은 다음과 같다.

 

 

① 재귀함수 이용

 

예: 집합 {a, b, c, d}에서 {a,b}는 a,b는 포함되어 있고 c,d는 포함되어 있지 않다.

 

포함안될 때와 될 때 두 가지 경우를 checked[]배열에 표시하고, 재귀함수로 돌린다.

즉, 각 원소에 대하여, (포함X, 포함X, 포함X, 포함X) ~ (포함O, 포함O, 포함O, 포함O) 까지를 모두 탐색한다.

 

public static void main(String[] args) {
	String[] arr = {"a", "b", "c", "d"};
	boolean[] checked = new boolean[arr.length]; //포함여부 체크

	makeset1(arr, checked, 0); // 1.재귀함수 이용
}

private static void makeset1(String[] arr, boolean[] checked, int index){

	if(index >= arr.length){
		for(int i=0; i<arr.length; i++){
			if(checked[i])
				System.out.print(arr[i]+" ");
		}
		System.out.println();
		return;
	}

	checked[index] = false; //arr[index]가 포함안될 때
	makeset1(arr, checked, index+1);

	checked[index] = true; //arr[index]가 포함될 때
	makeset1(arr, checked, index+1);
        
}

 

 

 

 

② 비트 이동 연산자 <<,>> 이용

 

   - 비트 이동 연산자 란?

 

 X의 비트를 Y만큼 오른쪽/왼쪽으로 이동시키는 '비트를 이동시키는 연산자' 이다.

 

       

예시)

 

---

public static void main(String[] args) {
	String[] arr = {"a", "b", "c", "d"};

	makeset2(arr); // 2.비트 연산자 이용
}

private static void makeset2(String[] arr){

	for(int i=0; i < (1<<arr.length); i++){ // (1)
		for(int j=0; j<arr.length; j++){ // (2)
			if((i & (1<<j)) != 0){ // (3)
				System.out.print(arr[j]+" ");
			}
		}
		System.out.println();
	}
    
}

(1) 1<<arr.length == 1<<4 이므로, 1111을 왼쪽으로 4비트 이동한 수 이다.

    즉 0000 ~ 1111 까지의 경우를 탐색한다.

 

(2) arr.length는 비트 자리수를 의미한다.

    arr = {a,b,c,d} 인 경우에 - a,b,c,d를 비트로 나타내면 0000~1111까지 표현할 수 있고,

    표현에 따르면 arr.length=4의 비트 자리수를 갖는다.

    그러므로 비트 자리수만큼 탐색한다.

 

(3) 1<<j 는 0001, 0010, 0100, 1000 을 의미한다.

    0000~1111 을 0001, 0010, 0100, 1000 과 각각 AND 해서 나온 수가 0이 아니면 출력한다.

    공집합인 경우 == i=0000일 때를 제외하고 arr의 부분집합이 모두 출력된다.