경우의수를 비트마스크로 표현하는 법
(사과, 딸기, 포도) 중 에서 선택 할수 있는 총 경우의 수는 어떻게 될까요?
아래 그림과 같이 선택 할수 있습니다.
선택하는 경우를 1, 선택 안하는 경우를 0 으로 표현 할수 있습니다.
이를 이용해서, 경우의수 문제(조합, Combination, DFS)를 비트 마스크를 이용해서 해결 할수 있을거 같습니다.
1. 비트 마스크
비트 마스크는 이진수로 표현하여, 비트 연산자(&(AND연산자), |(OR연산자), ^(XOR연산자))를 이용하여 각각의 이진수의 값을 마스킹(가리다) 하여, 원하는 연산을 할수 있는 것 입니다.
4(십진수) => {1, 0, 0}(이진수)
2(십진수) => {0, 1, 0}(이진수)
1(십진수) => {0, 0, 1}(이진수)
위와 같이 십진수를 이진수로 표현 할수 있습니다. 이 이진수를 컴퓨터의 비트 입니다.
2. & (AND연산자)
AND연산자는 두 비트가 모두 1일 때, 1을 반환 합니다.
3. | (OR연산자)
OR연산자는 두 비트가 모두 1 또는 하나라도 1일때, 1을 반환
4. ^ (XOR연산자)
XOR연산자는 두 비트가 서로 다르면 1을 반환
5. << (시프트 연산자)
x<<y (시프트 연산자는)는 x를 y만큼 비트를 이동시킨다는 뜻 입니다.
예를들어, 1<<3은 0001(이진수)을 1000(이진수)으로 만들어 버립니다.
6. (사과, 딸기, 포도) 3가지 중에서 선택할수 있는 모든 경우의 수는?
1<<3은 {1,0,0,0}(이진수) 입니다. 그러면 (1<<3) > i 경우는 무엇이 있을까요?
- {1,0,0,0} 보다 작은 경우들
{0, 0, 0}
{1, 1, 1}
{1, 0, 0}
{0, 1, 0}
{0, 0, 1}
{0, 1, 1}
{1, 1, 0}
{1, 0, 1}
= 총 8가지 입니다.
이것을 java 소스 코드로 표현해 보면 다음과 같습니다.
for(int i=0; i<(1<<3); i++) {
System.out.println(i);
}출력 결과
물론, 위의 출력 된 값은 십진수 입니다.
7. (사과, 딸기, 포도) 중에서 2가지만 선택 하는 경우는?
{0, 1, 1}
{1, 1, 0}
{1, 0, 1}
이렇게 3가지가 나옵니다.
java에서는 Integer.bitCount()라는 정적 메소드가 있습니다. 이 메소드는 비트가 1인 개수를 반환해 줍니다. java 소스 코드로 구현해 봅니다.
for(int i=0; i < (1<<3); i++) {
if(Integer.bitCount(i) == 2) {
System.out.print(i + " ");
}
}출력 결과
물론, 위 출력결과는 십진수 입니다.
3(십진수) => {0, 1, 1}
5(십진수) => {1, 0, 1}
6(십진수) => {1, 1, 0}
8. 위 출력 결과 (3, 5, 6)을 이진수로 변환하고, 변환된 이진수를 배열의 인덱스로 변환 하려면?
j가 0 ~ 2인경우, (1<<j)는
{0, 0, 1} (= 포도 선택) (= 0(십진수) 선택)
{0, 1, 0} (= 딸기 선택) (= 1(십진수) 선택)
{1, 0, 0} (= 사과 선택) (= 2(십진수) 선택)
을 만듭니다.
여기서, i가 3(십진수) = {0, 1, 1}(이진수) 이라면,
i & (1<<j) 는
{0, 1, 1} & {0, 1, 0} = {0, 1, 0}
{0, 1, 1} & {0, 0, 1} = {0, 0, 1}
을 뽑아낼수 있습니다.
그러면, 3개 중, 2개를 선택하는 경우의 수를 코드로 나타내 보겠습니다.
for(int i = 0; i < (1<<3); i++) { //3개 중
if(Integer.bitCount(i) == 2) { //2개를 선택하는 경우
for(int j = 0; j < 3; j++) { //{1,0,0},{0,1,0},{0,0,1}을 j로 만들어 놓음
if(((1<<j) & i) > 0) { //선택된 i라는 경우의수의 위치값을 출력
System.out.print(j+" ");
}
}
System.out.println(); //다음의 경우의수로 넘어감
}
}출력 결과
위와 같이 출력 됨을 알수 있습니다. 이것을 String 배열을 만들어 출력시키면 아래와 같습니다.
String[] fruits = {"사과", "딸기", "포도"};
for(int i = 0; i < (1<<3); i++) { //3개 중
if(Integer.bitCount(i) == 2) { //2개를 선택하는 경우
for(int j = 0; j < 3; j++) { //{1,0,0},{0,1,0},{0,0,1}을 j로 만들어 놓음
if(((1<<j) & i) > 0) { //선택된 i라는 경우의수의 위치값을 출력
System.out.print(fruits[j] + " ");
}
}
System.out.println(); //다음의 경우의수로 넘어감
}
}출력 결과
