[java][알고리즘] 비트마스크(Bit Mask)를 통한 배열의 부분집합 구하기

알고리즘을 이해하자 하자 하자 하자!

 

---

Bit Mask(비트 마스크)

정수의 이진수 표현을 활용한 기법으로, 
true / false 상태를 가지는 이진수를 자료구조로 사용하는 기법입니다.

 

비트 연산자 종류

AND 연산 (&) : 둘 다 1이라면 1, 아니면 0

// bit 1 : 0001 , 2 : 0010
// AND 연산, 둘다 1이라면 1, 아니면 0
System.out.println(1 & 2); // 0001 & 0010 = 0000
// out : 0

 

OR 연산 (|) : 둘다 0이라면 0, 아니면 1

// bit 1 : 0001 , 2 : 0010
// OR 연산, 둘다 0이라면 0, 아니면 1
System.out.println(1 | 2); // 0001 | 0010 = 0011
// out : 3

 

XOR 연산 (^) : 둘의 비트값이 다르면 1, 아니면 0

// bit 1 : 0001 , 2 : 0010
// XOR 연산, 둘의 비트값이 다르면 1, 아니면 0
System.out.println(5 ^ 2); // 0101 ^ 0010 = 0111
// out : 7

 

NOT 연산(~) : 모든 비트를 반전시킨 값을 리턴 (2의 보수)

// bit 1 : 0001 , 2 : 0010
// NOT 연산 : 모든 비트를 반전시킨 값을 출력 (2의 보수)
// 5 = 0000 .. 0000 0101(총 32자리수)
// 5 반전 시 1111 .. 1111 1010(가장 왼쪽 비트가 1이므로 음수, -6)
System.out.println(~5);
// out : -6

 

Shift 연산(<<, >>) : 일정 비트만큼 이동한 값을 리턴

// << 연산, 1을 2비트만큼 왼쪽으로 시프트
System.out.println(3 << 3); // 0011 << 3 = 0011000
// out : 24
 
// >> 연산, 5를 2비트만큼 오른쪽으로 시프트
System.out.println(5 >> 2); // 0101 >> 2 = 0001
// out : 1

 

비트 마스크를 활용한 배열의 부분집합 구하기

int[] arr = {1, 2, 3} 으로 주어졌을 때, arr의 모든 부분집합을 비트 마스킹을 통해 구하는 법을 알아보겠습니다.
* 기대 출력값 :  [[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

 

구현 코드

java

닫기 줄바꿈

// 공집합을 제외한 배열의 모든 부분집합을 리턴하는 메소드
    public static ArrayList<ArrayList<Integer>> generateSubsets(int[] arr){
        int n = arr.length;
        ArrayList<ArrayList<Integer>> totalSubset= new ArrayList<>();
 
        for (int i = 1; i < (1 << n); i++) {
            // 내부 루프를 순회하며 원소의 부분집합을 collect하는 list
            ArrayList<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++){
                if ((i & (1 << j)) > 0) {
                    subset.add(arr[j]);
                }
            }
            totalSubset.add(subset);
        }
        return totalSubset;
    }

 

결과값 출력

int[] arr = {1, 2, 3};
System.out.println(generateSubsets(arr));
// out : [[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

 

구현 원리

1. 외부 루프 : for (int i = 1; i < (1 << n); i++)

1.  i는 1부터 (1 << n) -1 까지 순회합니다.
2. 즉, 배열의 크기인 3 을 적용했을 시 (1 << 3) 은 이진수로 1000(2), 십진수로 8 입니다.
3. i는 십진수 8 에 -1 을 한  7 까지 순회하며, 순회 단위마다 i 는 1비트씩 증가할 예정입니다.

 

2. 내부 루프 : for (int j = 0; j < n; j++)

1. j는 0부터 n -1 까지 순회합니다.
2. 즉, 배열의 크기인 3 을 적용했을 시 j = 0, 1, 2 순서로 순회합니다. 
3. j는 각 원소를 순회하며 원소를 부분집합에 넣을지 말지 결정합니다. 

 

3. 조건 : if ((i & (1 << j)) > 0), subset.add(arr[j])

* 편의를 위해 이진수는 0000(2) 로 표현하겠음

1. 외부 루프 (i = 1) → 0001(2)
   • 내부 루프 j 는 0부터 2까지 순회하며, 1 << j 를 통해 각 비트를 확인합니다.
     • j = 0일 시 1 << j = 0001(2) 입니다.
       • i = 0001(2), j = 0001(2) 이므로 & 연산을 통해 0001(2) 값을 얻게 됩니다. 
       • 0001(2) > 0 이므로 j = 0 번째 원소인 1을 subset에 넣습니다.
     • j = 1일 시 1 << j = 0010(2) 입니다.
       • i = 0001(2), j = 0010(2) 이므로 & 연산을 통해 0000(2) 값을 얻게 됩니다. 
       • 0000(2) 값은 0보다 크지 않으므로 j = 1 번째 원소는 미포함합니다.
     • j = 2일 시 1 << j = 0100(2) 입니다.
       • i = 0001(2), j = 0100(2) 이므로 & 연산을 통해 0000(2) 값을 얻게 됩니다. 
       • 0000(2) 값은 0보다 크지 않으므로 j = 2 번째 원소는 미포함합니다.
     • j의 루프 종료 시 [1] 이라는 부분집합이 도출됩니다.
2. 외부 루프 (i = 2) → 0010(2)
   1. 내부 루프 j 는 0부터 2까지 순회하며, 1 << j 를 통해 각 비트를 확인합니다.
      • j = 0일 시 1 << j = 0001(2) 입니다.
        • i = 0010(2), j = 0001(2) 이므로 & 연산을 통해 0000(2) 값을 얻게 됩니다. 
        • 0000(2) 값은 0보다 크지 않으므로 j = 0 번째 원소는 미포함합니다.
      • j = 1일 시 1 << j = 0010(2) 입니다.
        • i = 0010(2), j = 0010(2) 이므로 & 연산을 통해 0010(2) 값을 얻게 됩니다. 
        • 0010(2) > 0 이므로 j = 1 번째 원소인 2를 subset에 넣습니다.
      • j = 2일 시 1 << j = 0100(2) 입니다.
        • i = 0010(2), j = 0100(2) 이므로 & 연산을 통해 0000(2) 값을 얻게 됩니다. 
        • 0000(2) 값은 0보다 크지 않으므로 j = 1 번째 원소는 미포함합니다.
      • j의 루프 종료 시 [1] 이라는 부분집합이 도출됩니다.
3. ... 동일한 과정으로 i의 외부 루프가 순환하며 부분집합을 도출합니다.
4. 외부 루프 (i = 7) → 0111(2)
   
   1. 내부 루프 j 는 0부터 2까지 순회하며, 1 << j 를 통해 각 비트를 확인합니다.
      • j = 0일 시 1 << j = 0001(2) 입니다.
        • i = 0111(2), j = 0001(2) 이므로 & 연산을 통해 0001(2) 값을 얻게 됩니다. 
        • 0001(2) > 0 이므로 j = 0 번째 원소인 1을 subset에 넣습니다.
      • j = 1일 시 1 << j = 0010(2) 입니다.
        • i = 0111(2), j = 0010(2) 이므로 & 연산을 통해 0010(2) 값을 얻게 됩니다. 
        • 0010(2) > 0 이므로 j = 1 번째 원소인 2를 subset에 넣습니다.
      • j = 2일 시 1 << j = 0100(2) 입니다.
        • i = 0111(2), j = 0100(2) 이므로 & 연산을 통해 0100(2) 값을 얻게 됩니다. 
        • 0100(2) > 0 이므로 j = 2 번째 원소인 3를 subset에 넣습니다.
      • j의 루프 종료 시 [1, 2, 3] 이라는 부분집합이 도출됩니다.

 

이로써 최종적으로 [1] , [2], [1, 2] ... [1, 2, 3] 까지의 모든 부분집합이 리턴됩니다.

 

구현 알고리즘 시간 복잡도 : O(2^n * n)

• 외부 루프 : O(2^n) : 1부터 1 << n -1까지 순회하며 총 2^n번 반복
• 내부 루프 : O(n) : 배열의 길이에 비례하여 n번 반복
• 총 시간 복잡도 : O(2^n * n)

 

 

비트마스크에 대해 알아봤습니다.

---

REFERENCE

클릭 시 깃허브로 이동합니다.