[240612 TIL] 완전탐색, 비트연산자

완전탐색

완전탐색은 가능한 모든 경우의 수를 전부 탐색하여 정답을 찾는 알고리즘 방법입니다. 이 방법은 문제 해결에 있어서 가장 기본적이고 직관적인 접근 방식으로, 문제의 모든 가능한 해를 생성하고 이를 모두 검사하여 최적의 해를 찾습니다.

완전탐색은 보통 다음과 같은 경우에 사용됩니다:

1. 문제의 입력 크기가 작을 때
2. 최적의 해를 반드시 찾아야 할 때
3. 문제 해결을 위한 다른 더 효율적인 알고리즘을 모르거나 구현하기 어려울 때

완전탐색의 단점은 일반적으로 시간 복잡도가 매우 높다는 것입니다. 가능한 모든 경우를 모두 탐색하기 때문에 입력 크기가 커지면 시간 내에 문제를 해결하기 어려울 수 있습니다.

예제: 모든 부분 집합 찾기

다음은 주어진 집합의 모든 부분 집합을 찾는 예제를 자바스크립트로 구현한 것입니다. 이는 완전탐색의 전형적인 예입니다.

function findAllSubsets(arr) {
    const subsets = [];
    const n = arr.length;

    // 부분 집합의 수는 2^n개
    const totalSubsets = Math.pow(2, n);

    for (let i = 0; i < totalSubsets; i++) {
        const subset = [];
        for (let j = 0; j < n; j++) {
            // i의 j번째 비트가 1인지 확인
            if (i & (1 << j)) {
                subset.push(arr[j]);
            }
        }
        subsets.push(subset);
    }

    return subsets;
}

// 예제 테스트
const arr = [1, 2, 3];
console.log(findAllSubsets(arr));
// 출력: [ [], [ 1 ], [ 2 ], [ 1, 2 ], [ 3 ], [ 1, 3 ], [ 2, 3 ], [ 1, 2, 3 ] ]

설명

1. 부분 집합의 수:
   • 주어진 집합의 부분 집합의 수는 (2^n)입니다. 여기서 (n)은 집합의 원소 수입니다.
2. 비트마스크 기법:
   • 각 부분 집합은 0부터 (2^n - 1)까지의 숫자로 표현할 수 있습니다.
   • 각 숫자의 비트는 집합의 각 원소가 부분 집합에 포함되는지를 나타냅니다.
   • 예를 들어, arr = [1, 2, 3]이고 숫자 5 (이진수로 101)은 부분 집합 [1, 3]을 나타냅니다.
3. 비트 연산:
   • i & (1 << j)는 숫자 i의 j번째 비트가 1인지 확인하는 방법입니다.
   • 만약 1이면 해당 원소를 부분 집합에 추가합니다.

이 방식으로 우리는 모든 부분 집합을 찾아낼 수 있습니다. 이 예제는 입력 크기가 작을 때는 매우 유용하지만, 입력 크기가 커질수록 비효율적일 수 있습니다. 이는 완전탐색의 전형적인 특징입니다.

비트연산자

비트 연산자 <<는 좌항의 비트들을 우항에서 지정한 수만큼 왼쪽으로 이동시키는 연산입니다. 예를 들어, 1 << 2는 1의 비트를 두 칸 왼쪽으로 이동시키므로 4(이진수 100)가 됩니다.

이제, 부분 집합을 찾는 코드에서 비트 연산 i & (1 << j)가 어떻게 작동하는지 자세히 설명하겠습니다.

비트 연산자 <<와 &의 사용

i & (1 << j)는 숫자 i의 이진 표현에서 j번째 비트가 1인지 확인하는 연산입니다. 이를 통해 부분 집합에 어떤 요소를 포함시킬지를 결정할 수 있습니다.

1. 1 << j는 숫자 1을 왼쪽으로 j비트 이동시킵니다.
   • 예를 들어, j가 2이면 1 << 2는 4(이진수 100)이 됩니다.
2. i & (1 << j)는 숫자 i의 j번째 비트가 1인지 확인합니다.
   • & 연산자는 비트 AND 연산을 수행합니다. 두 비트가 모두 1일 때만 결과가 1이 됩니다.
   • 예를 들어, i가 5(이진수 101)이고 j가 0이면 1 << 0은 1(이진수 001)이 됩니다. 따라서 5 & 1은 1(이진수 001)이므로 i의 0번째 비트는 1입니다.

예제 설명

다음은 배열 [1, 2, 3]의 모든 부분 집합을 찾는 과정에서 비트 연산이 어떻게 작동하는지 예를 들어 설명합니다.

코드

function findAllSubsets(arr) {
    const subsets = [];
    const n = arr.length;
    const totalSubsets = Math.pow(2, n);

    for (let i = 0; i < totalSubsets; i++) {
        const subset = [];
        for (let j = 0; j < n; j++) {
            if (i & (1 << j)) {
                subset.push(arr[j]);
            }
        }
        subsets.push(subset);
    }

    return subsets;
}

// 예제 테스트
const arr = [1, 2, 3];
console.log(findAllSubsets(arr));

실행 과정

1. i = 0 (이진수 000):
   • j = 0: 0 & (1 << 0) -> 0 & 1 -> 0 (포함 안 함)
   • j = 1: 0 & (1 << 1) -> 0 & 2 -> 0 (포함 안 함)
   • j = 2: 0 & (1 << 2) -> 0 & 4 -> 0 (포함 안 함)
   • 부분 집합: []
2. i = 1 (이진수 001):
   • j = 0: 1 & (1 << 0) -> 1 & 1 -> 1 (포함)
   • j = 1: 1 & (1 << 1) -> 1 & 2 -> 0 (포함 안 함)
   • j = 2: 1 & (1 << 2) -> 1 & 4 -> 0 (포함 안 함)
   • 부분 집합: [1]
3. i = 2 (이진수 010):
   • j = 0: 2 & (1 << 0) -> 2 & 1 -> 0 (포함 안 함)
   • j = 1: 2 & (1 << 1) -> 2 & 2 -> 2 (포함)
   • j = 2: 2 & (1 << 2) -> 2 & 4 -> 0 (포함 안 함)
   • 부분 집합: [2]
4. i = 3 (이진수 011):
   • j = 0: 3 & (1 << 0) -> 3 & 1 -> 1 (포함)
   • j = 1: 3 & (1 << 1) -> 3 & 2 -> 2 (포함)
   • j = 2: 3 & (1 << 2) -> 3 & 4 -> 0 (포함 안 함)
   • 부분 집합: [1, 2]
5. i = 4 (이진수 100):
   • j = 0: 4 & (1 << 0) -> 4 & 1 -> 0 (포함 안 함)
   • j = 1: 4 & (1 << 1) -> 4 & 2 -> 0 (포함 안 함)
   • j = 2: 4 & (1 << 2) -> 4 & 4 -> 4 (포함)
   • 부분 집합: [3]

이와 같은 방식으로 모든 부분 집합을 찾을 수 있습니다. 각 i에 대해 j번째 비트가 1인지 확인하고, 1이면 해당 요소를 부분 집합에 추가합니다. 이렇게 하면 총 2^n개의 부분 집합을 구할 수 있습니다.