[JAVA] 비트 연산자를 이용하여 조합 & 부분집합 & 부분집합 여부파악

아래 배열을 계속 쓸 것이다.

int[] arr = new int[]{1,2,3};

 

# 부분 집합 구하기

 

코드 생각 없이 그냥 부분 집합을 구한다고 하면 어떻게 구할까??

 

• 1
• 2
• 3
• 1,2
• 1,3
• 2,3
• 1,2,3

그렇다면 비트 마스크로 한다면 아래처럼 될 것이다.

 

• 100
• 010
• 001
• 110
• 101
• 011
• 111

1 = 선택함을 의미

0= 선택하지 않음을 의미

 

예를 들어, 위 처럼 "011" 이라면 arr 의 1은 선택하지 않고 2와 3을 선택함을 의미한다.

 

그래서 "001" 부터 "111" 까지 루프를 도는 코드는 아래와 같다.

 

for(int i=1;i<1<<3;i++){
...
}

 

 

i 가  "011" 라면 어떻게 배열에서 순회 하여 적절히 출력할까??

 

답은 & 연산이다.

 

원소가 3개 있으므로 첫번째 원소를 선택함을 의미하는 "100"

두번째 원소를 선택함을 의미하는 "010"

세번째 원소를 선택함을 의미하는 "001"

 

를 이용 한다.

 

 

예를 들어 "011" 과 "100","010","001" 을 각각 & 연산하면 

 

결과는 0(2),10(2),1(2) 이된다. & 연산해서 0보다 큰 경우만 체크해주면 원하는 대로 "011" 에서 두번째 원소와 세번째 원소만 적절하게 체크 할 수 있다.

 

부분 집합을 구하는 코드는 아래와 같다. ( i 가 1인 것은 공집합 제거)

for(int i=1;i<1<<3;i++){
    for(int j=0;j<3;j++){
        if((i & (1<<j)) >0){
        ...
        }
    }
}

 

좀더 일반화 하자. (공집합 포함)

 

int[] arr = ...

for(int i=0;i<1<<arr.length;i++){
    for(int j=0;j<arr.length;j++){
        if((i&1<<j) > 0){
         ...
        }
    }
}

 

 

# 조합 구하기

 

조합도 멋지게 구할 수 있다.

 

알고리즘 테스트 쓰도록 만들어 놔야겠다.

 

    static ArrayList<List<Integer>> nCkV2(int[] arr,int k){
        ArrayList<List<Integer>> ret = new ArrayList<>();
        int n = arr.length;
        for(int i=0;i<1<<n;i++){
            int cnt = 0;
            for(int j=0;j<n;j++){
                if((i & 1<<j)>0) cnt++;
            }
            if(cnt==k){
                List<Integer> tmp = new ArrayList<>();
                for(int j=0;j<n;j++){
                    if((i & 1<<j) > 0){
                        tmp.add(arr[j]);
                    }
                }
                ret.add(tmp);
            }
        }
        return ret;
    }

 

 

# 부분집합 여부 판단하기

 

0001 은 0111 의 부분 집합이다.

0010 은 0111 의 부분 집합이다.

0101 은 0111 의 부분 집합이다.

...

 

어떻게 판단 했는가?

 

x 와 y 의 부분집합이라면 (x&y) == x 인지 확인하면 된다.

 

 

0011 &  0111  의 결과는 0011 일것이며 

 

이는 0011 == 0011 이므로 0011 은 0111의 부분 집합이다.