비트 연산자를 이용한 순열과 부분집합

비트 연산자의 기본을 이해하기 위한 설명 및 사용법

 

비트 연산자를 사용하는 이유가 무엇인가?

일반적으로 비트 연산자는 이미 자신이 방문한 곳을 체크해주기 위한 boolean배열을 이용해서 나타내는 곳에 사용한다.

하지만 단순히 비트연산자를 방문한 곳을 체크해주기 위한 용도로 사용된다는 것은 이해가 어렵다.

 

예를 들어 총 10곳의 방문체크를 해줘야 하는 곳을 만들게 된다면 boolean visit [10]; 이렇게 하면 쉽게 해결될 것이다.

그렇다면 이것을 비트 연산자로 나타내게 되면 0000000000 이렇게 총 10자리가 되어 int형으로 나타나게 될 것이다.

 

이렇게 하면 int형은 4바이트 boolean은 10바이트 6바이트 밖에 차이가 나지 않는다.

 

그렇다면 굳이 이 6바이트 차이 때문에 비트 연산자를 사용하는가?

 

이 visit배열을 인스턴스 변수로 가진 DFS를 생각해보자

 

이렇게 보게 된다면 총 재귀 함수가 100번 일어날 것이고 각각의 재귀마다 10바이트짜리를 가지고 있기에 

1000바이트가 사용될 것이다.

 

그럼 비트 연산자를 사용한다면 어떻게 될 것인가?

 

비트 연산자를 사용하게 되면 각각의 재귀마다 4바이트를 가지고 있어 600바이트가 사용될 것이다.

 

이렇게 보면 별로 차이가 나지 않는데 할 수 있는데 재귀가 만약 10000번 이런 식으로 돌아간다면 많은 용량의 차이가 날 것이다.

 

이렇기 때문에 각각의 방문한 곳을 체크하는 값을 넘겨줄 때 용이하다. BFS에서 또한 마찬가지이다.

 

비트 연산자를 이용하게 된다면 3가지의 기본을 이해해야 한다.

 

1. 1<<n2^n을 가진다. n은 비트의 자리라고 생각하면 된다. 0000 이렇게 비트가 존재한다면 

이렇게 각각의 자리를 나타낼 수 있다.

 

2.  i & (1<< j)

   

   이 계산 결과는 i의 오른쪽에서 j번째 비트가 1인지 아닌지를 의미한다.

   

    i 번째 가 0이라면 AND 연산자에 의해 0을 반납하게 된다. 결국 그 위치에 있는지 알아내는 것으로 

    if( visit [j]==0 )을 확인하는 것이라고 보면 된다.

 

3. i | (1 << j) 

 

   이 계산 결과는 i의 기존 비트열에 추가적으로 오른쪽에서 j번째 비트를 1로 만드는 것이다.

 

   i의 j번째가 0 이든 1이든 관계없이 j로 값을 변경해준다 visit [j]==1 처리해주는 것과 같다고 보면 된다.

 

1. 비트 연산자를 이용한 순열 문제

 

2. 비트 연산자를 이용한 부분 집합 문제

 

이렇게  순열과 부분집합 문제를 비트 연산자를 이용하여 접근한 문제를 해보았다.