자바 알고리즘 Subset 알아보기

- Subset(부분 집합)

어떤 집합에 포함되는 집합

어떤 집합의 '부분'이 되는 집합

Ex) {1, 2, 3}의 부분 집합은 공집합, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}

 

* 조합에서 n까지 가면 부분집합

 

* 부분집합은 재귀를 통하여 가장 효율성 있게 표현 가능 !!!!!

private static void subset(int depth, int len) {
    // 모든 원소에 대해 선택/비선택을 하여 subset을 생성
    // depth가 N에 도달하면 하나의 subset이 완성된 상태
    if (depth == N) {
        // subset이 완성되었으므로 필요한 작업 수행
        totalCnt++;
        // copyOfRange(배열, start, len)는 배열의 0번 인덱스부터 len개의 원소를 복사
//        System.out.println(Arrays.toString(Arrays.copyOfRange(numbers, 0, len)));
        return;
    }

    // 원소 선택
    numbers[len] = input[depth];
    subset(depth + 1, len + 1);

    // 원소 선택 안 함 (비선택)
    subset(depth + 1, len);
}

 

* 비트마스터를 통한 부분집합 표현

- 비트마스터 확인!!!

비트마스터 shift메소드를 통해서 해당 값에 있는지 없는지 / 추가 까지 가능

>> N : 비트를 N번 오른쪽으로 이동 => 2의 N승으로 나눈 효과
0000 1000 8>>2
0000 0010

int n = 8;
System.out.println("8>>2 :"+ (n>>2));
출력: 8>>2 : 2

<< N : 비트를 N번 왼쪽으로 이동 => 2의 N승으로 곱한 효과
System.out.println("8<<2 :"+ (n<<2)); 
출력: 8<<2 :32

 

subset의 개수는 2의 n승 개이므로
0 : 원소를 선택 안함 1:원소를 선택함

0 => 0000: 원소 하나도 선택안한 서브셋
1 => 0001: 맨 끝의 원소 하나를 선택한 서브셋
2 => 0010: 맨 끝에서 두번째 원소 하나를 선택한 서브셋
3 => 0011: 맨 끝의 두개의 원소를 선택한 서브셋

 size-1 1111 : 모든 원소를 선택한 서브셋

시간 복잡도 2^n

import java.util.Arrays;

public class SubsetGenerator {
    static int N;
    static int[] subset;
    static int[] input; // 원소 배열 (예: {1, 2, 3, 4})
    
    public static void main(String[] args) {
        N = 4; // 예시로 4개의 원소를 사용
        input = new int[] {1, 2, 3, 4};  // 입력 배열 예시
        subset = new int[N]; // 부분 집합을 나타낼 배열 (1이면 선택, 0이면 선택 안함)
        
        long stime = System.currentTimeMillis();  // 시작 시간 기록
        
        // 0부터 2^N - 1까지 반복 (모든 부분집합을 확인)
        for (int i = 0, size = 1 << N; i < size; i++) {
            // i를 이진수로 표현하여 부분 집합을 생성
            for (int j = 0; j < N; j++) {
                if ((i & (1 << j)) != 0) {
                    subset[j] = 1; // 해당 원소 선택
                }
            }

            // 부분 집합을 출력
            print();
            
            // 다음 부분 집합을 구하기 위해 subset을 0으로 초기화
            Arrays.fill(subset, 0);
        }
        
        long etime = System.currentTimeMillis();  // 종료 시간 기록
        System.out.printf("%dms\n", etime - stime);  // 실행 시간 출력
    }
    
    // 부분 집합을 출력하는 메소드
    public static void print() {
        System.out.print("[");
        for (int i = 0; i < N; i++) {
            if (subset[i] == 1) {
                System.out.print(input[i] + " ");  // 선택된 원소 출력
            }
        }
        System.out.println("]");
    }
}

 

 

-조합

* 부분집합에서 r를 선택하면 조합을 구할 수도 있다

private static void combi(int depth, int r) {
    // r이 원하는 조합의 크기(R)에 도달하면 현재 조합을 출력
    if (r == R) {
        System.out.println(Arrays.toString(numbers));
        return;
    }

    // 입력 배열의 끝에 도달하면 더 이상 진행할 필요 없음
    if (depth >= N) {
        return;
    }

    // 현재 원소를 선택
    numbers[r] = input[depth];
    combi(depth + 1, r + 1);

    // 현재 원소를 비선택
    combi(depth + 1, r);
}
	}

 

*But 조합에서 가장 효율성 좋은 꼭 알아야 하는 코드!!!!!!!!!

private static void combi(int depth, int start) {
    // 모든 조합을 뽑은 경우 (depth가 r에 도달한 경우)
    if (depth == r) {
        testcase++;
//        System.out.println(Arrays.toString(numbers));  // 조합을 출력하려면 주석을 해제
        return;
    }

    // start부터 n까지 반복하며 조합을 생성
    for (int i = start; i < n; i++) {
        numbers[depth] = input[i];  // 현재 depth에 input[i] 값을 선택
        combi(depth + 1, i + 1);    // 다음 depth로 진행, start를 i+1로 설정
    }
}

 

 

*부분집합을 이용한 문제 풀이

- 백준 2961번

package boj.bronze;

import java.util.Scanner;

public class Main_2961_도영이가만든맛있는음식 {
    
    static int N;
    static int[][] input;
    static int min = Integer.MAX_VALUE; // 최소 차이를 찾기 위한 초기값 (최대값으로 설정)
    
    // depth: 현재 탐색 중인 재료의 인덱스
    // sour: 선택된 재료들의 신 값의 곱
    // bitter: 선택된 재료들의 쓴 값의 합
    // pick: 고른 재료의 개수 (pick > 0이면 최소값을 구할 때 사용)
    static void cook(int depth, int sour, int bitter, int pick) {
        // 재료가 모두 탐색되었을 때
        if (depth == N) {
            // 최소 1개 이상의 재료를 고른 경우만 계산
            if (pick > 0) {
                min = Math.min(min, Math.abs(sour - bitter)); // 신 값과 쓴 값의 차의 최솟값 계산
            }
            return;
        }
        
        // 재료를 선택한 경우 (sour 값은 곱셈, bitter 값은 더하기)
        cook(depth + 1, sour * input[depth][0], bitter + input[depth][1], pick + 1);
        
        // 재료를 선택하지 않은 경우 (현재 재료는 포함하지 않음)
        cook(depth + 1, sour, bitter, pick);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // N은 재료의 개수
        N = sc.nextInt();
        input = new int[N][2]; // 각 재료의 sour, bitter 값을 저장할 배열
        
        // 재료의 sour과 bitter 값 입력 받기
        for (int i = 0; i < N; i++) {
            input[i][0] = sc.nextInt();  // sour 값
            input[i][1] = sc.nextInt();  // bitter 값
        }
        sc.close(); // 입력 종료
        
        // 재료를 선택하는 모든 경우의 수를 탐색
        cook(0, 1, 0, 0);
        
        // 결과 출력 (최솟값)
        System.out.println(min);
    }
}