[Algorithm] 완전탐색 (JS) - 3 : 비트마스킹(Bitmasking)

- 나올 수 있는 모든 경우의 수가 둘 중 하나로부터 나오는 경우 유용하게 사용할 수 있다

 

1. 비트마스킹이란 ? 

- 정수 값을 이진 비트로 표현하여 비트 단위 연산을 사용해 특정한 작업을 수행하는 기법

- 웹에서는 플래그, 설정, 퍼미션 등을 효율적으로 관리할 수 있다.

- 일반적으로 비트 연산자(AND, OR, XOR, NOT, SHIFT)를 사용한다.

 

- React에서 비트마스킹을 사용하여 여러 설정 옵션을 관리할 수 있다.

- '&' 는 비트 AND 연산자로, 각 정수의 이진표현에서 같은 위치에 있는 비트를 비교하여 두 비트가 모두 1인 경우에만 결과의 해당 위치의 비트를 1로 설정한다.

- 예를 들어, 5 & 4 는 0101 과 0100의 비트AND연산을 시행하면

0101

0100

0100 (답)

이렇게 된다.

 

React 예시

Read Access 와 Write Acess 만 렌더링이 된다.

 

2. 완전탐색에서의 사용

- 부분집합이나 순열 같은 문제에 대해서 완전탐색을 수행할 때, 효율적이고 간결한 코드로 구현할 수 있다.

 

3. 완전탐색 문제 예시 

- n개의 원소를 가진 집합의 모든 부분집합을 찾는 문제에서 사용할 수 있다.

- 각 원소가 부분집합에 포함되거나 포함되지 않거나 두 가지 상태를 가질 수 있으므로, 전체 경우의 수는 2^n 이다.

- 완전탐색을 수행하면서 각각의 정수 값을 이진수로 나타내고, 1인 비트의 위치에 해당하는 원소를 선택하여 부분집합으로 구성할 수 있다.

비트마스킹은 이중for문이 핵심이다.

보조설명

배열 arr = [1, 2, 3] 이 있을 때, 모든 부분집합을 찾는 문제를 생각해봅시다. 이 배열의 길이는 3이므로, n = 3입니다.
완전 탐색을 수행하기 위해 2^n (2의 n제곱)인 2^3 = 8가지의 조합을 살펴봅니다. 각 조합은 0부터 2^n - 1까지의 정수로 표현됩니다.
이진수로 나타낼 때, 다음과 같은 8가지 조합이 생성됩니다.

000 - 빈 집합
001 - {1}
010 - {2}
011 - {1, 2}
100 - {3}
101 - {1, 3}
110 - {2, 3}
111 - {1, 2, 3}

이제 이진수의 각 비트에 따라 배열의 원소를 선택하는 방법을 살펴보겠습니다.

for (let j = 0; j < n; j++): 배열의 원소를 순회하기 위한 for문입니다.
if ((i & (1 << j)) !== 0): j번째 비트가 1인지 확인하는 조건문입니다.
1 << j: j번째 비트만 1인 이진수를 생성합니다. (예: j = 0이면 001, j = 1이면 010)
i & (1 << j): i와 (1 << j)의 비트 AND 연산을 수행합니다. 이렇게 하면 j번째 비트가 1인지 확인할 수 있습니다.
subset.push(arr[j]): j번째 비트가 1인 경우, arr[j]를 현재 부분집합인 subset에 추가합니다.

 

아 너무 오래전에 배웠던거라 기억이 잘 안난다..