[알고리즘_개념] 비트마스크 연산, 부분집합의 표현

부분집합이란?

wiki백과 '부분집합'정의의 일부

예를 들어,

집합 A = {a, b, c, d}가 있다고 하면, 

A의 부분집합인 B는 {}, {a}, {b}, ... {a,b}, ... {a, b, c}, ... {a,b,c,d}, 16(2^4)가지수로 표현될 수 있다.

 

비트마스크 연산을 이용한 부분집합의 프로그램으로의 구현

부분집합은 집합에서 각각 원소가 있다(1) 혹은 없다(0)의 경우의 수로 볼 수 있는데, 이러한 경우로 보면 '비트마스크 연산'을 이용해 표현할 수 있다.

구현과정을 두가지로 나눌 수 있다.

1. 부분집합을 이진수로 표현하기

2. 각각 이진수를 부분집합으로 변환해서 출력하기. (1이면 해당 원소 출력, 0이면 continue;)

 

 

1. 각 원소를 이진수로 표현

다음은 집합 A = {a, b, c, d}의 부분집합을 이진수로 표현한 것이다.

(공집합은 다룰 필요가 없으므로 생략함.)



부분집합 원소에 맞게 표현한 순서지만, 이진수의 순서대로 나열한다면 0001-1111까지의 수가 표함된다.

1111은 10000의 바로 이전에 있는 값이며, 10000은 비트마스크 연산에 의하여 다음과 같이 표현할 수 있다.

10000 = (1<<4)

또, 여기서 4는 부분집합의 개수를 의미한다.

 

따라서 이를 for loop로 표현한다면 다음과 같다.

코드복사는 아래

char[] A = {'a', 'b', 'c', 'd'};
int setSize = A.length;

for(int i=1; i< 1<<4; i++){
System.out.println("i :" + i + ", 이진수 i : " + Integer.toBinaryString(i));
}

결과

결과

 

2. 각각 이진수를 부분집합으로 변환해서 출력하기

 a) 비트연산자 간단하게 정리

           & (and연산자): 둘 다 1이어야 1, 하나라도 0이 포함되면 0

           | (or연산자): 둘 중 하나라도 1이면 1, 둘다 0이면 0

          ~ (not연산자) : 0이면 1, 1이면 0

          ^ (xor연산자) : 같으면 0, 다르면 1

b) 이진수를 부분집합으로

[Idea]

1 & (이진수) -> 이진수의 마지막 자리수가 나온다. 

코드복사는 아래

char[] A = {'a', 'b', 'c', 'd'};
int setSize = A.length;

for(int i=1; i< 1<<setSize; i++){
System.out.print("i :" + i + ", 이진수 i : " + Integer.toBinaryString(i) + ", subset : ");
//System.out.println(1&i);
for(int k=0; k<setSize; k++){
if((1& i>>k) == 0) continue;
System.out.print(A[A.length-1-k] + " ");
}
System.out.println();
}

결과

결과

-> 부분집합의 순서는 뒤집어졌지만 문제풀 때 문제 없을 것!

 

언제필요할까?

여러 문제에서 사용되지만, 개인적으로 카카오 2018 후보키문제가 대표적인 부분집합문제였다.

https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키 | 프로그래머스

 

백준의 '부분수열의 합' 문제는 위의 로직대로 한다면 바로 풀린다.

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합