[코테 알고리즘] 완전탐색(Brute Force) 알고리즘과 순열/조합

완전탐색(Brute Force)

---

모든 경우의 수를 시도해보는 방법
📌 Brute-Force: 무식하게 힘(컴퓨터의 연산능력)으로 찍어누르는 방법

⭐. 경우의 수
- 순열: 순서가 결과에 영향을 미치는 경우
- 조합: 순서가 결과에 영향을 미치지 않는 경우
- 부분집합: 각 요소가 포함한다 or 포함하지 않는다

[Permutation.java]

public class Permutation {
    static char[] arr;
    static int R;
    static int[] selection;
    static boolean[] isSelected;
    public static void permutation(int r) {
        // 종료조건
        if(r == R) {
            for(int i = 0; i < R; i++) {
                System.out.print(arr[selection[i]]);
            }
            System.out.println();
            return;
        }
        // 재귀적 확장
        for(int i = 0; i < arr.length; i++) {
            if(isSelected[i]) {
                continue;
            }
            isSelected[i] = true;
            selection[r] = i;
                              //  0  1  2 
                              //  A  B  C 
            permutation(r+1);
            // 백트래킹, 선택 -> 취소
            isSelected[i] = false;
        } 
    }
    public static void main(String[] args) {
        arr = new char[] {'A', 'B', 'C'};
        R = 2;
        selection = new int[R];
        isSelected = new boolean[arr.length];

        permutation(0);
    }
}

💡 사고과정
r은 현재 선택한 개수를
i는 문자의 인덱스를 의미한다 (0: 'A', 1: 'B', 2: 'C')

(i = 0)(i = 0부터)
AA => 중복 pass
AB => 종료 => 출력 => B 취소
AC => 종료 => 출력 => AC 취소

(i = 1)(i = 0부터)
BA => 종료 => 출력 => A 취소
BB => 중복 pass
BC => 종료 => 출력 => BC 취소

(i = 2)(i = 0부터)
CA => 종료 => 출력 => A 취소
CB => 종료 => 출력 => B 취소
CC => 중복 pass

[Combination.java]

public class Combination {
    static char[] arr;
    static int R;
    static int[] selection;
    static boolean[] isSelected;
    public static void combination(int r, int start) {
        //종료조건
        if(r == R) {
            for(int i = 0; i < R; i++) {
                System.out.print(arr[selection[i]]);
            }
            System.out.println();
            return;
        }
        // 재귀적 확장
        for(int i = start; i < arr.length; i++) {
            if(isSelected[i]) {
                continue;
            }
            isSelected[i] = true;
            selection[r] = i;
                           //  0  1  2 
                             //  A  B  C 
            combination(r+1, i);
            // 백트래킹, 선택 -> 취소
            isSelected[i] = false;

        }
    }
    public static void main(String[] args) {
        arr = new char[] {'A', 'B', 'C'};
        R = 2;
        selection = new int[R];
        isSelected = new boolean[arr.length];

        combination(0,0);
    }
}

💡 사고과정
r은 현재 선택한 개수를
i는 문자의 인덱스를 의미한다 (0: 'A', 1: 'B', 2: 'C')
int i = start때문에 '뒷문자 인덱스'는 '앞문자 인덱스'보다 같거나 큰 인덱스만 탐색하게된다

(i = 0)(i = start = 0부터)
AA => 중복 pass
AB => 종료 => 출력 => B 취소
AC => 종료 => 출력 => AC 취소

(i = 1)(i = start = 1부터)
BB => 중복 pass
BC => 종료 => 출력 => BC 취소

(i = 2)(i = start = 2부터)
CC => 중목 pass

[Subset.java]

public class Subset {
    static char [] arr;
    static int N;
    static int cnt = 0;
    static boolean [] isSelected;

    static void subset(int num) {
        // 종료조건
        if(num == N) {
            cnt++;
            for(int i=0; i<N; i++) {
                if(isSelected[i]) System.out.print(arr[i] + " ");
            }                
            System.out.println();
            return;
        }

        /// 분할 ///

        // 선택x
        isSelected[num] = false;
        subset(num+1);

        // 선택0
        isSelected[num] = true;
        subset(num+1);
    }
    public static void main(String[] args) {    
        arr = new char [] { 'A' , 'B' , 'C' , 'D'};
        N = arr.length;
        isSelected = new boolean [N];

        subset(0);

        System.out.println("부분집합의 총 개수 : " + cnt);
    }
}

💡 사고과정
각 자리마다 해당 자리의 문자를 포함하느냐 or 포함하지 않느냐를 따져주면 된다.