KB IT’s Your Life 4기 - Java 알고리즘 10일차

부분집합

원소들의 부분이 되는 집합
ex. {1,2,3} => 공집합, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
조합이라고 볼 수 있다.

* 구현방법 *

조합: 한자리 조합 + 두자리 조합 + 세자리 조합
비트마스크

멱집합

부분 집합을 모아둔 것

부분집합 구현

1자리~n자리까지 조합을 반복한다. (for문으로 n값 조정)

재귀함수 작성 (가장 머리아픔)

비트마스크 (가장 쉬움)

bit AND 연산 (false: 0, true: 1)
- 0&0 : 0 / 0&1 : 0 / 1&0 : 0 / 1&1 : 1 (AND)
- 0 0 : 0 / 0 1 : 1 / 1 0 : 1 / 1 1 : 1 (OR)

- 0: 0000 & 0001 = 0
- 1: 0001 & 0001 = 1
- 2: 0010 & 0001 = 0 / 0010 & 0010 = 2 
- 3: 0011 & 0001 = 1
- 4: 0100 & 0001 = 0
- 5: 0101 & 0001 = 1
- 6: 0110 & 0001 = 0
- 7: 0111 & 0001 = 1

즉, &0001을 했을 때, 0이라면 비교한 숫자의 네번째 자릿수가 0이라는 것이고, 1이라면 비교한 숫자의 네번째 자릿수가 1이라는 것이다.
&0010을 했을 때, 0이라면 비교한 숫자의 세번째 자릿수가 0이라는 것이고, 1이라면 비교한 숫자의 세번째 자릿수가 1이라는 것이다.
shift 연산
- <<
- >>
- >>>

package 재귀리뷰;

//중복배제
public class 경우의수4_부분집합 {
    static int[] arr ; //원소
    static boolean[] visited;//사용여부
    static int n ; //답의 길이
    static int[] result; //답저장배열
    
    public static void main(String[] args) {
        arr = new int[]{1, 2, 3};
        n = 3;
        visited = new boolean[n];
        powerSet(0); //재귀함수로 구현
//        bit(); //비트연산으로 구현
    }

//재귀함수
    static void powerSet(int depth) {
        if (depth == n) {
            printResult();
            return;
        }

        visited[depth] = false;
        powerSet(depth + 1);

        visited[depth] = true;
        powerSet(depth + 1);
    }

//비트연산
    static void bit() {
        for (int i = 0; i < 1 << n; i++) {
            for (int j = 0; j < n; j++) {
                if ((i & 1 << j) != 0)
                    System.out.print(arr[j] + " ");
            }
            System.out.println();
        }
    }

    static void printResult() {
        for (int i = 0; i < n; i++) {
            if (visited[i] == true)
                System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

백준 2961

package b2961;

import java.util.Scanner;

public class Main {
    private static int N;
    private static int sumS=1;
    private static int sumB=0;
    static int[] S;
    static int[] B;
    static int result=1000000000;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = new int[N];
        B = new int[N];
        for(int i=0;i<N;i++) {
            S[i] = sc.nextInt();
            B[i] = sc.nextInt();
        }
        bit();
        System.out.println(result);
        
    }
    
    static void bit() {
        for (int i = 0; i < 1 << N; i++) {
            for (int j = 0; j < N; j++) {
                if ((i & 1 << j) != 0) {
                    sumS*=S[j];
                    sumB+=B[j];
                    if(abs(sumS-sumB)<result) {
                        result=abs(sumS-sumB);
                    }
                }
            }
            sumS=1;
            sumB=0;
        }
    }
    
    static int abs(int a) { //절댓값
        if(a<0)
            a = -a;
        return a;
    }

}