[Algorithm] Brute-force - 조합, 순열, 부분 집합

 

완전 검색 (Exhaustive Search )

• Brute-force = generate-and-test
• 모든 경우의 수를 나열해보고 확인하는 기법
• 조합 / 순열 / 부분 집합

 

조합과 순열, 중복 조합과 중복 순열

import java.util.Arrays;
import java.util.Scanner;

// 210204

public class Comb_Per_DiceTest {
    static int[] numbers;
    static int N, totalCnt;
    static boolean[] isSelected;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 주사위 던진 횟수
        numbers = new int[N];
        isSelected = new boolean[7]; // 1~6 주사위 눈의 사용 여부

        int M = sc.nextInt(); // 던지기 모드
        totalCnt = 0;


        switch(M) {
            case 1:
                System.out.println("중복순열");
                dice1(0);
                break;
            case 2:
                System.out.println("순열");
                dice2(0);
                break;
            case 3:
                System.out.println("중복조합");
                dice3(0,1);
                break;
            case 4:
                System.out.println("조합");
                dice4(0, 1);
                break;
        } 
        System.out.println("총 경우의 수 : " + totalCnt);
        sc.close();
    }

    // 1. 중복 순열 : nㅠr ==> n^r
    // 6개 중 3개 : 6 * 6 * 6 = 216
    private static void dice1(int cnt) {
        if (cnt == N) {
            totalCnt++;
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for (int i = 1; i <= 6; i++) {
            numbers[cnt] = i; // i는 뽑은 주사위 눈
            // cnt는 자리수
            dice1(cnt + 1);
        }
    }

    // 2. 순열 : nPr => n * (n-1) * (n-2) ...
    //          6P3 => 6 * 5 * 4 = 120
    private static void dice2(int cnt) {
        if (cnt == N) {
            totalCnt++;
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for (int i = 1; i <= 6; i++) {
            if (isSelected[i]) continue;
            numbers[cnt] = i; // i는 뽑은 주사위 눈
                            // cnt는 자리수
            isSelected[i] = true;
            dice2(cnt + 1);
            isSelected[i] = false;
        }
    }

    // 3. 중복 조합 : 6H3 : n+r-1Cr 8C3 = 56
    private static void dice3 (int cnt, int start){
        if (cnt == N) {
            totalCnt++;
            System.out.println(Arrays.toString(numbers));
            return;
        }

        // 조합 - 순서 의미 x
        for (int i = start; i <= 6; i++ ) {
            numbers[cnt] = i;
            dice3(cnt+1, i);

        }
    }

    // 4. 조합 nCr : 6C3 = 20
    private static void dice4 (int cnt, int start){
        if (cnt == N) {
            totalCnt++;
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for (int i = start; i <= 6; i++ ) {
            numbers[cnt] = i;
            dice4(cnt+1, i+1);

        }
    }

}

static void combination(int cnt, int L, int total) {
  if (total > M) {
      return;
  }

  if (cnt == 2) {
    maxWeight = Math.max(maxWeight, total);
    return;
  } 

  if (L == N) {
      return;
  }

    combination(cnt+1, L+1, total + snack[L]);
    combination(cnt, L+1, total);
} // 

 

부분 집합

import java.util.Scanner;

// 210204

public class S1_SubSetTest {

    static int N, totalCnt;
    static int[] 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);
        System.out.println("총 경우의 수 : " + totalCnt);

    }

    // 현 원소의 부분집합의 구성에 반영
    private static void generateSubset(int cnt) {
        if (cnt == N) {
            ++totalCnt;
            // 선택된 숫자들만 출력
            for (int i=0; i<N; i++) {
                System.out.print( (isSelected[i] ? input[i] : "X") + "\t");
            }
            System.out.println();
            return;
        }

        // 선택
        isSelected[cnt] = true;
        generateSubset(cnt+1);
        // 비선택
        isSelected[cnt] = false;
        generateSubset(cnt+1);
    }

}

 

부분집합의 합 구하기

import java.util.Scanner;

//210204

public class S2_SubSetSumTest {

    static int N, totalCnt, S;
    static int[] input;
    static boolean[] isSelected;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt(); // 더해서 S가 되는지 알아본다.

        input = new int[N];

        isSelected = new boolean[N];

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

        generateSubset(0);
        System.out.println("총 경우의 수 : " + totalCnt);

    }

    // 현 원소의 부분집합의 구성에 반영
    private static void generateSubset(int cnt) {
        if (cnt == N) {
            int sum = 0, selectedCnt = 0;
            // 선택된 숫자들만 더한다.

            for (int i=0; i<N; i++) {
                if(isSelected[i]) {
                    sum+= input[i];
                    selectedCnt++; // 공집합 제외하기 위해
                }
            }

            if (sum == S && selectedCnt>0) {
                ++totalCnt;
                for (int i=0; i<N; i++) {
                    if (isSelected[i]) System.out.print(input[i] + "\t");
                }
                System.out.println();
            }

            return; // 더 이상 부분집합을 생성하지 못하면
        }

        // 선택
        isSelected[cnt] = true;
        generateSubset(cnt+1);
        // 비선택
        isSelected[cnt] = false;
        generateSubset(cnt+1);
    }

}