subset

🙋‍♂️ 들어가며

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

back-tracking vs bit-masking

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

아래 Java 코드는 combination 관점에서 접근한 핵심 풀이입니다. 입력 조건과 시간·공간 복잡도를 함께 고려하여 불필요한 연산을 줄이는 방향으로 설계했습니다.

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

위 구현은 subset의 제약 조건을 만족하도록 자료구조 선택과 반복 범위를 최적화한 결과입니다.

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

            []
        /         \
      [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 N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] arr = {1, 6, 13, 9, 27, 100};
		N = arr.length;
		
		
		for (int i = 0; i < N; i++) {
			int[] subset = new int[N];
			subset[0] = arr[i];
			comb(i+1, arr, subset, 1);
		}
	}
	
	
	static void comb(int depth, int[] arr, int[] subset, int size) {
		// 1. 최대 깊이 도달시 출력
		if (depth == N) {
			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. 선택
		comb(depth+1, arr, subset, size+1);
		
		// 2-2. 미선택
		comb(depth+1, arr, subset, size);
	}
	

	
	
	
}
}

다음은 비스마스킹이다

시간복잡도는 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));
		}
		
		
		
	}	
}