[알고리즘] 부분집합 & 조합 + 비트 연산자

개요

SSAFY 교육 정리

부분집합 (Powerset)

• 비트 연산자

연산자	연산자의 기능
&	비트 단위로 AND 연산 예) num1 & num2
|	비트 단위로 OR 연산을 한다. 예) num1 | num2
^	비트 단위로 XOR 연산을 한다. (같으면 0 다르면 1) 예) num1 ^ num2
~	단항 연산자로서 피연산자의 모든 비트를 반전시킨다. 예) ~num
<<	피연산자의 비트 열을 왼쪽으로 이동시킨다. 예) num << 2
>>	피연산자의 비트 열을 오른쪽으로 이동시킨다. 예) num >> 2

• 부분집합의 수
  - 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2ⁿ개
  - 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.
  - 예)
  

• 반복문을 이용하여 부분집합 구하기 - 의사코드

sel = {0, 0, 0, 0}
for i in 0 to 1:
    sel[0] = i                        // 0번째 원소
    for j in 0 to 1 :
        sel[1] = j                    // 1번째 원소
        for k in 0 to 1 :
            sel[2] = k                // 2번째 원소
            for l in 0 to 1:
                sel[3] = 1            // 3번째 원소
                print(sel)            // 생성된 부분집합 출력

• 반복문을 이용하여 부분집합 구하기 - java

import java.util.Arrays;

public class 부분집합_반복문 {
	int[] nums = {1, 2, 3};
    public static void main(String[] args) {
    	int N = nums.length;
        int[] selected = new int[N];
        
        for(int i = 0; i < 2; i++) {
        	selected[0] = i;
            for(int j = 0; j < 2; j++) {
            	selected[1] = j;
                for(int k = 0; k < 2; k++) {
                	selected[2] = k;
                    System.out.println(Arrays.toString(selected));
                }
            }
        }
    }
}

• 비트마스킹을 이용하여 부분집합 구하기 - 의사코드

//N : 원소의 개수
// 부분집합의 수만큼 반복 돌리기
for (int i = 0; i < (1 << N); i++){
    //i라는 부분집합에 원소 확인하기
    for(int j = 0; j < N; j++){
    //해당 i 값에 j번째 비트가 존재한다면
        if((i & (1 << j)) > 0 ){
            // 처리
        }
    }
}

• 비트마스킹을 이용하여 부분집합 구하기 - java

import java.util.Arrays;

public class 부분집합_비트마스킹 {
	static int[] nums = {1, 2, 3};
    public static void main(String[] args) {
    	// 비트마스킹을 이용해보자!
        int N = 3;
        
        // i는 모든 부분집합을 의미한다.
        for(int i = 0; i < (1<<N); i++) {
        	//i가 부분집합 중 1개라는 것은 알겠어.
            //그런데 i가 무슨 원소를 가진 부분집합인지는 몰라
            //i가 무슨 원소를 가진 부분집합인지 검사를 해야 해!
            //N개의 원소를 검사를 한다.
            String tmp = "";
            for(int j = 0; j < N; j++) {
            	//i의 j번째 비트에 해당 값이 있는지 체크!
                if((i & (1<<j)) > 0) {
                	// 해당 j번째의 요소가 이번 부분집합에는 포함되어 있습니다.
                    tmp += String.valueOf(nums[j]);
                }
            }
            System.out.println(tmp);
        }
    }
}

• 재귀 호출을 이용하여 부분집합 구하기 - 의사코드

//sel[] : 해당 원소 포함 여부 저장
// n : 원소의 개수, k : 현재 depth
static void powerset(int n, int k){
    if(n==k) {            // Basis Part
        print(sel);
        return;
    }                    // Inductive Part
    sel[k] = false;        // k번 요소 X
    powerset(n, k+1);    // 다음 요소 포함 여부 결정
    sel[k] = true;        // k번 요소 0
    powerset(n, k+1);    // 다음 요소 포함 여부 결정

• 재귀 호출을 이용하여 부분집합 구하기 - java

public class 부분집합_재귀 {
	static int[] nums = {1, 2, 3};
    static int N;
    static boolean[] selected; // 해당 요소 선택 했다!
    
    public static void main(String[] args) {
    	N = 3;
        selected = new boolean[N];
        
        powerset(0);
    }
    
    //메소드를 작성할 때 최대한 파라미터를 심플하게
    //idx : 해당 숫자를 포함할 지 안할 지 결정해야 함.
    public static void powerset(int idx) {
    	//base case: 재귀를 빠져 나갈 수 있는 조건
        // 모든 숫자를 넣을 지 / 말지에 대한 판단 끝났어!
        if(idx == N) {
        	String tmp = "";
            for(int i = 0; i < N; i++) {
            	if(selected[i]) {
                	tmp += String.valueOf(nums[i]);
                }
            }
            System.out.println(tmp);
            return;
        }
        
        // recursive : 나 자신을 다시 호출하는 조건
        selected[idx] = true; // idx번째 숫자를 사용했어!
        powerset(idx+1); //다음 숫자를 고려해~
        
        selected[idx] = false; // idx번째의 숫자를 사용하지 않겠어!
        powerset(idx+1); //다음 숫자를 고려해~
    }
}

조합 (Combination)

• 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합(Combination)이라고 부른다.
• 조합의 수식
  
  
• 재귀 호출을 이용한 조합 생성 알고리즘 - 의사코드

data[] : n개의 원소를 가지고 있는 배열
sel[] : r개의 크기의 배열, 조합이 임시 저장될 배열
comb(n, r)
    IF r == 0 : print_array()
    ELSE IF n < r : RETURN
    ELSE
        sel[r - 1] <- data[n-1]
        comb(n - 1, r - 1)
        comb(n - 1, r)

• 재귀 호출을 이용한 조합 생성 알고리즘 - java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 조합_재귀 {
	// 재귀를 이용한 조합
    static int[] nums = {1, 2, 3, 4};
    static int N = 4;
    static int R = 2;
    
    static boolean[] selected = new boolean[R]; // 내가 선택한 숫자
    
    static List<int[]> list = new ArrayList<>();
    
    public static void main(String[] args) {
    	combination(0, 0);
        
//        for(int[] numArr : list) {
//        	System.out.println(Arrays.toString(numArr));
//        }
    }
    //idx : 내가 이번 깊이에서 고려할 숫자!
    //sidx : 현재 뽑을 자리
    public static void combination(int idx, int sidx) {
    	//base case
        if(sidx == R) {
        	//list.add(selected);
            System.out.println(Arrays.toString(selected));
            return;
        }
        // recursive case
        // 경계값 결정
        for(int i = idx; i <= N-R+sidx; i++) {
        	selected[sidx] = nums[i];
            combination(i+1, sidx+1);
        }
    }
}

data[] : n개의 원소를 가지고 있는 배열
sel[] : r개의 크기의 배열, 조합이 임시 저장될 배열
sidx : sel 배열의 인덱스, idx : data 배열의 인덱스
comb(idx, sidx)
    IF sidx == r : print_array()
    ELSE IF idx >= n : RETURN
    ELSE
        sel[sidx] <- data[idx]
        comb(idx+1, sidx+1)
        comb(idx+1, sidx)

• 반복문을 이용한 조합 생성 알고리즘

// { 1, 2, 3, 4 } 중 원소 3개를 뽑아보자.
FOR i from 1 to 2 {
    FOR j from i + 1 to 3 {
        FOR k from j + 1 to 4 {
            print i, j, k;
         }
      }
}

• 반복문 + 재귀를 이용한 조합 생성 알고리즘

data[] : n개의 원소를 가지고 있는 배열
sel[] : r개의 크기의 배열, 조합이 임시 저장될 배열
sidx : sel 배열의 인덱스, idx : data 배열의 인덱스
comb(idx, sidx)
    IF sidx == r : print_array()
    ELSE
        FOR i from idx to N-R+sidx
            sel[sidx] <- data[i]
               comb(idx+1, sidx+1)