알고리즘을 풀다보면 모든 경우의 수를 봐야하는 경우가 생긴다.
이럴 때 여기안에서도 머리를 쓰면 귀찮아지는 경우가 있는데 코드에는 비트연산이라는게 존재한다.
비트연산
Java에서는 |, & 가 있는데 각각 Or, And 를 의미한다. 이는 자료형이 int형이더라도 컴퓨터에 들어가는 데이터 형태에 대해 논리연산을 한다. 즉, 2진수의 형태에서 비트 연산을 한다는 의미이다.
|(or)연산
보다시피 양측 어느쪽이 1이라면 그부분은 1이된다. 때문에 '또는'이라고도 한다.
&(and)연산
얘는 좀 깐깐한 친구인데 양측이 무조건 1이어야 1이 된다. 때문에 '그리고'라고도 한다.
<<연산
평소에 필기할때 방향으로 썼던놈인데 여기서 보니 반갑다.
이 연산은비트를 좌측으로 움직이라는 말이다.
예를 들어 3<<2 라고 한다면 3을 좌측으로 2만큼 움직인다는 말이다.
이게 말이 좀 이상한데, 3이라는 숫자는 컴퓨터에게는 0011이다. 따라서 이를 움직이면
아래와 같이 된다.
하나는 아쉬우니 한번만 더하자면 3<<3은 3을 좌측으로 3만큼 움직인다는 말이다.
이후 움직여지고 나오는 빈칸은 0으로 채우게 된다.
>>연산
<<연산관 반대이다. 즉, <<연산이 좌측으로 움직였다면 이놈은 우측으로 움직인다.
알지 모르지만 컴퓨터에게있어서 음수의 표현은 맨 마지막(맨 우측)에 있는 부호 비트로 표시된다.
그렇다면 >>연산으로 움직여지고 우측에 생기는 공백은 무엇으로 채울까?
이는 해당 부호비트가 된다. 예를 들어 24>>3이라고 한다면
그리고 -24>>3 연산은
와 같이 이루어진다.
즉, 부호비트를 좌측에 채워넣는것을 알 수 있다.
부분조합
부분 조합을 알려고 했는데 왠 이상한 비트 연산만 배웠다.
이제 비트연산을 가지고 조합의 모든 경우의 수를 뽑아볼 차례이다.
만약 3개의 숫자를 0포함 모두 뽑았을 때, 경우의 수는 8개이다.
경우의 수
X
1
2
2 1
3
3 1
3 2
1 2 3
그리고 0부터 7까지 2진수로 표현하면 아래와 같은 그림이 나온다.
어라? 경우의 수와 뭔가 비슷해 보인다.
여기서 자릿수를 좀더 표현하면
위와 같이 나온다.
즉, 0 ~ 7까지의 2진수는 3의 모든 경우의 수를 알 수 있다.
이를 통해 0~ 15(16), 0 ~ 31(32) 등 쭉 알 수 있는데 이게 결국 2의 제곱이라는 것을 알 수 있다.
그런데 어떻게 이것을 통해 경우의 수를 모두 뽑을까?
이때 우리가 위에서 한 비트 연산을 통해 각 위치에 값을 가져올 수 있다.
위치값 가져오기
0 ~ 7의 2진수 값이 3개를 뽑을때 모든 경우의 수가 나왔다. 여기서 3을 예시로 들어보자면
3의 이진수는 011이다.
그리고 우리는 위에서 &연산을 배웠다. 이 연산은 같은 위치안에 값이 둘다 1이여야만 1을 내뱉는다.
따라서 3과 &연산을 통해 0이 아닌 숫자는 1과 2이다.
&연산을 통해 나온 1과 2는 3을 이진수로 바꿨을 때의 1의 위치이다.
즉 0~7까지 3번만 돌리면 경우의 수를 뽑아 낼 수 있게된다.
코드
public static void makeCase(int N){
int[] arr =new int[N];
for(int i = 1; i <= N; i++){
arr[i-1] = i;
}
//여기서 만들어진 배열에서 부분집합을 뽑는다.
//꼭 연속된 숫자가 아니라 무작위 숫자여도 해당하는 배열의 부분집합을 표시
for(int i = 1; i< (1<<N); i++){ //경우의 수는 2ⁿ만큼 나오기때문에 <<연산으로 처리
for(int j=0;j<arr.length;j++){
if((i&1<<j) > 0){ //1을 <<연산으로 움직여서 2의 제곱, 즉, 2진수 자리수를 만들어낸다.
System.out.print(arr[j] + " ");
}
}
System.out.println();
}
}