subset

🙋‍♂️ 들어가며

이번 시간에는 subset을 구하는 방법을 2개로 알아볼 것이다

back-tracking vs bit-masking

배열이 이렇게 있다고 가정하자

int[] arr = {1, 6, 13, 9, 27, 100};

백트랙킹으로 보면 다음과 같이 진행될 것이다

            []
        /         \
      [1]          []
     /   \        /   \
  [1,6]  [1]    [6]    []

2가지로 나누기에 시간복잡도 -> O(2^N)

✅ 코드 (back-tracking)

package boj;

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;

import java.util.Arrays;


public class Main {
	static int r;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] arr = {1, 6, 13, 9, 27, 100};
		r = arr.length;
		
		int[] subset = new int[r];
		
		lets_find(0, 0, arr, subset);
	}
	
	
	
	static void lets_find(int depth, int size, int[] arr, int[] subset) {
		// 1. 최대깊이 도달시
		if (depth == r) {
			int[] answer = new int[size];
			for (int i = 0; i < size; i++) {
				answer[i] = subset[i];
			}
			System.out.println(Arrays.toString(answer));
			return;
		}
		
		
		// 2. 최대 깊이 도달 못했으면
		subset[size] = arr[depth];
		
		// 2-1. 선택
		lets_find(depth + 1, size + 1, arr, subset);
		
		// 2-2. 미선택
		lets_find(depth + 1, size, arr, subset);
	}
	
	
	

	
	
	
}

다음은 비스마스킹이다

시간복잡도는 O(N^2)

실제로 n <= 20 일때 많이 사용한다

코드는 다음과 같다

✅ 코드 (bit-masking)

package boj;

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;

import java.util.Arrays;


public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] arr = {1, 6, 13, 9, 27, 100};
		int total = 1 << arr.length;
		int n = arr.length;
		
		for (int bit = 0; bit < total; bit++) {
			int[] subset = new int[n];
			int size = 0;
			for (int mask = 0; mask < n; mask++) {
				if ( (bit & (1<<mask) ) != 0 ) {
					subset[size] = arr[mask];
					size++;
				}
			}
			// 출력
			int[] result = new int[size];
			for (int i = 0; i < size; i++) {
				result[i] = subset[i];
			}
			System.out.println(Arrays.toString(result));
		}
		
		
		
	}	
}