[Java] 비트 마스크에 대해서 알아보자

N개중 M개를 뽑아서 검사를 해야하는 완전 탐색의 경우에는 다양한 방식이 존재합니다.

우선 개수가 적을 때는 반복문을 통해 모든 탐색이 가능합니다.

N=3, M=2라 생각해서 3개중 2개를 뽑아보면 다음과 같이 작성 할 수 있습니다.

3개중 2개를 선택해야 하므로 2중 반복문을 통해 간단히 구현을 해보았습니다.

int N = 3, M = 2;
for(int i=0;i<N;i++) {
    for(int j=0;j<N;j++) {
        if(i==j) continue;
        System.out.println(i+"       "+j);
    }
}

 출력 결과는 다음과 같습니다.

0       1
0       2
1       0
1       2
2       0
2       1

3개중 2개를 택하는 모든 경우를 잘 표현하고 있는 것을 볼 수 있습니다. 

▶ 모든 조합을 구하는 경우지만 중복된 조합을 피하고 싶으면 j의 범위를 i 이상 부터 시작하도록 하면됩니다.

이렇게 반복문을 통해서도 구할 수 는 있지만.. N=10, M=6이라고 생각해보면 6중 반복문을 적용해야 합니다. 숫자가 늘어날 수록 반복문의 개수가 늘어나기때문에 구현하기가 점점 어려워집니다.

따라서 이럴경우는 다른 방법으로 작성하는 것이 쉬울 것입니다. 그럼 다른 방법 2가지에 대해서 알아보겠습니다.

1) 재귀를 통한 DFS 탐색

첫 번째 방법은 재귀를 통한 방법입니다. 위의 똑같은 예제를 재귀를 통해 구현해 보겠습니다.

재귀로 DFS 탐색을 할 때 핵심은 자신을 포함하는가 포함하지 않는가 됩니다. 따라서 이 경우도 선택 개수 변수 cnt를 올려주면서 2가 될 경우 cnt가 0,1 일 때 저장해둔 숫자를 출력해 주었습니다.

▶ 실제 문제에서 DFS를 적용시켜 준다면 방문 배열을 하나 따로 만들어서 진행을 해주었을 겁니다.

static int[] arr = new int[2];
private static void solve(int idx,int cnt) {
    // cnt(선택 개수)가 2개가 되면 출력
    if(cnt==2) {
        System.out.println(arr[0]+"  "+arr[1]);
        return;
    }
    
    // idx가 2를 벗어나면 종료
    if(idx>=3) return;
    
    // 자신을 포함
    arr[cnt] = idx;
    solve(idx+1,cnt+1);
    // 자신을 미포함
    solve(idx+1,cnt);
}

출력은 다음과 같습니다.

0       1
0       2
1       2

3가지 중 2가지가 출력되는것을 보실 수 있습니다. 아까 반복문 과의 엄청난 차이점이라면 N과 M이 커지더라도 반복문으로 걸어준 cnt의 개수와 오류를 막기위한 idx의 범위만 바꿔준다면 된다는 점입니다.

▶ 출력도 바로 안찍고 반복문을 적용해준다면 수정할 게 없어질 것입니다.

이렇게 재귀를 통한 조합 완전 탐색을 해보았습니다. 그럼 다음으로 비트 마스크에 대해 알아보겠습니다.

비트 마스크는 말 그대로 비트 연산을 통해 숫자들을 선별해준다는 의미입니다.

▶ 마스크 단어 자체가 무언가 가리는 느낌을 주는걸 느끼실 수 있습니다!!

비트 연산에 대한 간단한 내용은 다음의 주소에서 확인 하실 수 있습니다.

▶ https://blog.naver.com/wltjs610/221367990285

이제 이 비트 연산으로 어떻게 모든 조합을 낼 수 있는지 보겠습니다.

바로 위의 예제를 적용 해본다면 3개의 숫자를 1과 0으로 구분 짓는 것입니다.

000부터 111까지 다양한 숫자들을 만들 수 있습니다.

따라서 비트 마스크를 사용하려면 우선 3개의 비트 값이 필요하게 됩니다. 우리는 이 값을 Shift 연산을 통해서 얻을 수 있습니다. 예제의 경우 3개의 숫자이므로 1<<3의 연산을 하면 1이 왼쪽으로 3칸을 이동하므로 1000이 만들어 지게됩니다. 

반복문을 돌릴 경우 i<(1<<3) 으로 조건을 걸어주면 1000 보다 하나작은 111 까지의 조건들을 따져주게 됩니다. 이 때, 0부터 시작을 하면 000부터 111까지의 조건을 만들 수 있고, 저희가 필요한 2개일 경우 즉, 1이나 0이 2개일 경우를 따져준다면 비트를 조합의 조건으로 이용할 수 있게됩니다.

그럼 반복문의 조건부터 하나씩 살펴보겠습니다.

for(int i=0;i<(1<<3);i++) {
    System.out.println(i);
}

i의 조건을 (i<<3)으로 둔 뒤 i값을 출력해 보았습니다. 000부터 1000 전 까지의 조건을 따저주므로 0부터 7이 출력될 것입니다. 출력은 다음과 같습니다.

0
1
2
3
4
5
6
7

이제 000 부터 111 까지 진행이 된다는 것을 알 수 있습니다. 따라서 011 101같은 1값을 2개 가진 값들을 뽑아내 보겠습니다. Java에서는 이 비트 값이 1인 개수를 알려주는 메소드가 존재합니다. 바로 다음의 메소드입니다.

Integer.bitCount()

 Integer.bitCount(n)을 넣어주면 비트가 1인 개수를 return해 줍니다. 

▶ 오라클의 Jave Doc(https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#bitCount(int))을 보시면 Integer의 static 메소드로 지정이 되어서 1인 비트 값의 개수를 return 해준다는 것을 볼 수 있습니다.

따라서 Java에서는 이 bitCount() 함수를 통해 쉽게 원하는 조합을 얻을 수 있습니다.

for(int i=0;i<(1<<3);i++) {
    if(Integer.bitCount(i)==2) {
        System.out.println(i);
    }
}

bitCount(2)를 통해서 1이 2개인 값들을 뽑았습니다. 출력은 다음과 같습니다.

3
5
6

3은 011 , 5는 101, 마지막으로 6은 110으로 잘 출력이 되는 것을 확인할 수 있습니다. 이제 이 값들을 가지고 각 자리를 index로 보고 처리를 해주시면 됩니다.

▶ 즉, 2개를 뽑아냈다면 해당 숫자를 비트 별로보면서 해당 비트값이 1이라면 해당 index를 출력해주면 됩니다.

이 때, 숫자를 살펴보기 위해서도 비트를 살펴보아야 하므로 비트 연산이 들어가게 됩니다.

앞서 반복문의 조건을 알아볼 때, 1<<n을 하면 1을 왼쪽으로 n칸 밀어내는 것을 알고 있습니다. 이 원리를 이용해서 3개의 비트를 만들어 준뒤 & 연산을 통해 비교를 하게됩니다.
▶ 001, 010, 100 을 만들어 준 뒤 예를들어 3인 011과 각 각 & 연산을 하면 비트가 1인 두 자리는 001, 010으로 0 이상인 값이 나오게 됩니다. 코드를 통해 살펴보겠습니다.

Index가 3인 예제이므로 반복문을 0~3번 돌려 1을 Shift 시켜줍니다.

1<<j;

이제 j에 따라서 001, 010, 100이 만들어 질 것입니다. 따라서 얻고자 하는 값이 i 값과 & 연산을 진행해 줍니다.

(1<<j)&i;

그럼 3을 예제로들면 001, 010이 얻어집니다. 이제 이 값들은 0보다 큰 값이므로 조건문을 통해 각 비트(Index)를 얻어냅니다.

if(((1<<j)&i)>0)

해당 비트가 1로 조건문 안으로 들어오게 되면 해당 j 값을 출력해줍니다. 전체 코드는 아래와 같습니다.

for(int i=0;i<(1<<3);i++) {
    if(Integer.bitCount(i)==2) {
        for(int j=0;j<3;j++) {
            if(((1<<j)&i)>0) {
                System.out.print(j+"       ");
            }
        }
        System.out.println();
    }
}

출력은 다음과 같습니다.

0       1
0       2
1       2

[백준] 2309번 일곱 난쟁이 문제를 풀어보면서 비트 마스크로 풀이를 해보면서, 비트 마스크에 대해서 정리를 해보았습니다. 비트 마스크에 대해서 아직 익숙하지 않다면 위와같은 문제들을 통해 풀어보시면 좋을 것 같습니다!!