알고리즘 기법 비트연산(비트 마스크)

기법

알고리즘 기법 [비트연산(비트 마스크)] 부분 합

 

체감 난이도

골드 1

 

설명

비트연산을 이용한 부분합 구하기
비트마스크는 수열의 각 원소에 대해 포함 여부를 나타내는 이진수입니다. 예를 들어, 수열에 3개의 원소가 있으면, 각 원소를 포함하거나 제외하는 경우는 총 8가지입니다(이진수로 000부터 111까지).각 비트가 1이면 해당 원소를 포함하고, 0이면 제외합니다.

배열이 [3, 1, 2]일 때, 모든 부분수열을 비트마스크로 나타내면 다음과 같습니다:

비트마스크 000: 아무 원소도 포함하지 않음 → 부분수열 [] (합 = 0)
비트마스크 001: 마지막 원소만 포함 → 부분수열 [2] (합 = 2)
비트마스크 010: 두 번째 원소만 포함 → 부분수열 [1] (합 = 1)
비트마스크 011: 두 번째와 마지막 원소 포함 → 부분수열 [1, 2] (합 = 3)
비트마스크 100: 첫 번째 원소만 포함 → 부분수열 [3] (합 = 3)
비트마스크 101: 첫 번째와 마지막 원소 포함 → 부분수열 [3, 2] (합 = 5)
비트마스크 110: 첫 번째와 두 번째 원소 포함 → 부분수열 [3, 1] (합 = 4)
비트마스크 111: 모든 원소 포함 → 부분수열 [3, 1, 2] (합 = 6)

예시: 부분 수열의 합 구하기
수열: ListA = [3, 1, 2]부분 수열의 합을 비트연산으로 구하려면, 1 << n 만큼의 비트마스크를 순차적으로 사용하여 각 부분 수열을 나타냅니다.
비트마스크 3비트는 8개의 경우가 나옵니다 (0부터 7까지). 이 값을 사용하여 각 부분 수열의 합을 구할 수 있습니다.

비트마스크로 부분집합 생성
i & (1 << j): i라는 비트마스크의 j번째 비트가 1인지를 확인합니다.
ex ) 
i가 (111)이라 가정

i & (1 << 0)
111 & 001 이므로, 일치하는 것 외에는 모두 0으로 만든다. 따라서
-> 001 이 남는다. 

i & (1 << 1)
111 & 010 이므로, 일치하는 것 외에는 모두 0으로 만든다. 따라서
-> 010 이 남는다. 

i & (1 << 2)
111 & 100 이므로, 일치하는 것 외에는 모두 0으로 만든다. 따라서
-> 100 이 남는다. 

 

장점

효율성: 2^n번 반복해서 부분 수열을 구하지만, 각 부분 수열의 합을 한 번에 계산하므로 시간 복잡도가 비교적 낮습니다.직관성: 수열을 비트마스크로 처리하면 부분 수열의 포함 여부를 직관적으로 알 수 있습니다.

비트연산을 이용한 부분합 구하기는 매우 효율적이고, 특히 수열의 크기가 크지 않거나 부분 수열의 합을 빠르게 구해야 하는 경우에 유용합니다.

 

코드

public class Main {    public static void main(String[] args) {        int[] ListA = {3, 1, 2};  // 예시 수열        int N = ListA.length;        long targetSum = 4;  // 우리가 찾고자 하는 부분합 (예: 4)        // 부분합 계산        List<Long> subSums = new ArrayList<>();        generateSubSums(ListA, subSums);        // 부분합 리스트 출력        System.out.println(subSums);        // 주어진 값과 일치하는 부분합 개수 세기        long count = 0;        for (long sum : subSums) {            if (sum == targetSum) {                count++;            }        }        System.out.println("부분합이 " + targetSum + "인 경우의 수: " + count);    }    // 비트마스크로 부분합 생성    private static void generateSubSums(int[] arr, List<Long> sums) {        int n = arr.length;        for (int i = 0; i < (1 << n); i++) {  // 2^n 가능한 부분집합            long sum = 0;            for (int j = 0; j < n; j++) {                if ((i & (1 << j)) != 0) {  // i의 j번째 비트가 1이면 arr[j]를 포함                    sum += arr[j];                }            }            sums.add(sum);        }    }}

 

알고리즘 기법을 이용한 문제 풀이 

https://www.acmicpc.net/problem/1208