[알고리즘] 비트 마스킹으로 '부분 집합' 구해보기 - JAVA

부분 집합이란?

A라는 집합이 있고 B라는 집합이 있다고 가정해보자.
A라는 집합이 B라는 집합에 속하면 A는 B의 부분 집합이 된다.
예를 들어, 집합 {1, 2, 3}의 부분 집합은 {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} 으로 자기 자신까지 포함해서 총 8개가 된다. 즉 부분 집합의 개수는 원래 집합의 원소의 개수를 N이라고 할 때, 2^N 개라고 할 수 있다.

---

먼저 비트 연산자를 알아보자.

 

위에서 설명한 부분 집합의 개수를 구하는 것을 비트 연산자로

1 << N

 

이렇게 나타 낼 수 있다.

1을 2진수로 나타냈을 때 0001이고, N이 3일 때 3만큼 왼쪽으로 비트를 이동시키면 1000으로 8이 된다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int n = arr.length;
        
        //i는 모든 부분집합
        for (int i = 0; i < (1 << n); i++) {
        
        	//n개의 원소를 검사하여 어떤 원소를 가진 부분 집합인지 검사
            for (int j = 0; j < n; j++) {
            
            	//i의 j번 째 비트에 해당 값이 있는지 체크하기
                if ((i & 1 << j) != 0) {
                    System.out.print(arr[j] + " ");
                }
            }
            System.out.println();
        }

    }

}

 

n이 3이라고 할 때 1 << n은 1000(2)가 된다. 첫 번째 for문에서 i 는 1000(2) 전까지 증가하기 때문에 111(2) 까지 증가한다.

즉 i는

000

001

010

011

100

101

110

111

이렇게 증가한다.

 

j와 위 숫자들을 AND연산을 통해 1인 비트들을 찾아 인덱스처럼 사용할 수 있게 된다!

---

💡 결론

부분 집합을 구하는 방법에는 여러 가지가 있는데 그 중 비트마스킹으로 부분 집합을 구하는 알고리즘을 공부했다.

 

알고리즘 문제들 중에 조합을 뽑는 문제들은 무조건 n개중r을 뽑아야 하는 nCr문제로 주어지는데,

 

만약 nC1 , nC2, ... , nCn - 1 , nCn 을 모두 고려해봐야 할 경우라면 부분 집합 알고리즘을 사용할 수 있을 것 같다!