Featured image for [Java] 부분집합

[Java] 부분집합

작성자:

 

종류설명기호시간 복잡도
순열N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수nPrO(N!)
조합N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수nCrO(n! /( r! x (n-r)!))
부분집합N개의 원소로 부분집합을 만드는 모든 경우의 수nHrO(2^N)

집합에 포함된 원소들을 선택하는 것.

  • 멱집합 (Power set)
    • 주어진 집합의 모든 부분 집합들로 구성된 집합

원소들의 그룹에서 최적의 부분 집합을 찾는 문제가 많다.

Featured image for [알고리즘] 5215. 햄버거 다이어트
[알고리즘] 5215. 햄버거 다이어트
0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자. 1. C++ 가. 제출 #include #include using namespace std; const int MAXN = 20; int n, l, ret; int t[MAXN], k[MAXN]; void solve(int depth, int cal, int score){ if(depth == n){ if(cal ret){ ret = score; } return; } if(cal > l) return; score += t[depth]; cal … 더 읽기

(knapsack – 햄버거 다이어트)

1. 반복문

for i in 1 -> 0
    selected[1] <- i
    for j in 1 -> 0
        selected[2] <- j
        for k in 1 -> 0
            selected[3] <- k
            for m int 1 -> 3
                if selected[m] == 1 then
                    print m            
Code language: HTML, XML (xml)

2. 재귀 함수

input[]
isSelected[]

generateSubset(cnt)
    if(cnt == N)
        for m int 1 -> N
            if selected[m] == 1 then
                print m
    else
        isSelected[cnt] <- true
        generateSubset(cnt + 1)
        isSelected[cnt] <- false
        generateSubset(cnt + 1)
Code language: PHP (php)
import java.util.Scanner;

// N개의 원소를입력받아 가능한 모든 부분집합 생성
// 1<=N<=10
public class PowerSetTest {

    static int N, input[];
    static boolean isSelected[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N= sc.nextInt();
        input = new int[N];
        isSelected = new boolean[N];

        //입력
        for(int i=0; i<N; i++) {
            input[i] = sc.nextInt();
        }

        generateSubSet(0);

        sc.close();
    }

    private static void generateSubSet(int depth) {
        // 완성
        if(depth == N) {
            StringBuffer sb = new StringBuffer();
            for(int i=0; i<N; i++) {
                sb.append(isSelected[i] ? input[i] : "X").append("  ");
            }
            System.out.println(sb);
            return;
        }

        isSelected[depth] = true; // 포함
        generateSubSet(depth + 1);
        isSelected[depth] = false; // 미포함
        generateSubSet(depth + 1);
    }

}
Code language: JavaScript (javascript)

N개의 원소를 입력받아 가능한 모든 부분집합 생성하는 코드.

3. 부분집합의 합

import java.util.Scanner;

// N개의 원소를입력받아 가능한 모든 부분집합 생성
// 1<=N<=10
public class PowerSetSumTest {

    static int N, target, input[];
    static boolean isSelected[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N= sc.nextInt();
        target = sc.nextInt();
        input = new int[N];
        isSelected = new boolean[N];

        for(int i=0; i<N; i++) {
            input[i] = sc.nextInt();
        }

        generateSubSet(0, 0);

        sc.close();
    }

    private static void generateSubSet(int depth, int sum) {

        if(depth == N) { // 부분집합의 합이 목표합인지 확인
            if(sum!=target) return;
            StringBuffer sb = new StringBuffer();
            for(int i=0; i<N; i++) {
                if(isSelected[i]) sb.append(input[i]).append(" ");
            }
            System.out.println(sb);
            return;
        }

        isSelected[depth] = true;
        generateSubSet(depth + 1, sum + input[depth]);
        isSelected[depth] = false;
        generateSubSet(depth + 1, sum);
    }

}
Code language: JavaScript (javascript)

N개의 원소를 입력받고 모든 원소의 합이 목표합과 같은 부분집합을 찾는 코드.

3040번: 백설 공주와 일곱 난쟁이

3040번: 백설 공주와 일곱 난쟁이

4. 바이너리 카운팅

가. 비트 연산

연산자기능
&비트 AND 연산자. 두 비트가 모두 1이면 1을 반환하고, 그렇지 않으면 0을 반환한다.
^비트 XOR 연산자. 두 비트가 서로 다르면 1을 반환하고, 같으면 0을 반환한다.
~비트 NOT 연산자. 비트를 반전시킨다. 0은 1로, 1은 0으로 변환된다.
<<왼쪽 시프트 연산자. 비트를 왼쪽으로 지정된 수만큼 이동시킨다.
>>부호 있는 오른쪽 시프트 연산자. 비트를 오른쪽으로 지정된 수만큼 이동시킨다.
>>>부호 없는 오른쪽 시프트 연산자. 비트를 오른쪽으로 지정된 수만큼 이동시킨다.
  • 1<<n : 최하위 1비트를 오른쪽에서 n번 떨어진 위치로 옮긴다.
  • value & 1<<n : value에서 n번째 비트의 값을 거져오는 방법. (마스크 오프)
  • value | 1<<n : value에서 n번째 비트의 값을 1로 설정하는 방법. (마스크 온)

비트 하나는 2가지 상태를 표현할 수 있다.

이러한 특성을 활용해서 방문 여부, 선택 여부를 저장하기 위해서 사용할 수 있다.

공간복잡도 측면에서 압도적으로 유리하다.

시간복잡도 측면에서는 불리할 수 있다.

대략 27개 이하(2^27 = 연산 1억 = 1초) + 공간복잡도가 중요한 문제 → 비트마스킹.

(참고로 알파벳 개수가 26개다.)

Featured image for [알고리즘] 11723. 집합
[알고리즘] 11723. 집합
0. 문제 11723번: 집합 1. 문제 이해 메모리 제한 448MB. (java8 기준) 주어지는 x의 크기가 1 ≤ x ≤ 20라서 int 32비트로 부분집합을 충분히 표현할 수 있다. 비트 연산으로 풀기 … 더 읽기

(비트마스킹 활용 기초)

나. 바이너리 카운팅

원소 수에 해당하는 N개의 비트열을 이용한다.

n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미.

int arr[] = {3, 6, 7, 1, 5, 4};
int n = arr.length;

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();
    }
}
Code language: PHP (php)

가지치기를 효율적으로 할 수 있다면 재귀 함수로 구현하는 것이 더 빠를 수 있다.

댓글 남기기