조합(2)

public class Chap_04 {

    public static void main(String[] args) {
//      1. 조합
        System.out.println("== 조합 ==");
        //서로 다른 4명 중 주번 2명 뽑는것
        int n = 4;
        int r = 2;

        int pResult = 1;
        for (int i = n; i >= n - r + 1; i--) {
            pResult *= i;
        }

        int rResult = 1;
        for (int i = 1; i <= r; i++) {
            rResult *= i;
        }

        System.out.println("pResult = " + pResult / rResult);

        //      2. 중복 조합
        System.out.println("== 중복 조합 ==");
        // 후보 두명 유권자 3명 무기명 투표
        n = 2;
        r = 3;

        System.out.println("결과 :" + getCombination(n + r - 1, r));

    }

    static int getCombination(int n, int r) {
        int pResult = 1;
        for (int i = n; i >= n - r + 1; i--) {
            pResult *= i;
        }

        int rResult = 1;
        for (int i = 1; i <= r; i++) {
            rResult *= i;
        }

        return pResult / pResult;
    }
}

<연습문제>

// Practice
// 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 X, 중복 x)의 각 결과를 출력하시오
public class Practice_04 {
    void combination(int[] arr, boolean[] visited, int depth, int n, int r) {

        /*
        arr = 1234
        visited = 0000 -> 1000 -> 1100 -> 1110
        depth = 0 -> 1 -> 2 -> 3
        r = 3 -> 2 -> 1 -> 0 // 0에서 한번 걸려서 visited가 true인 애들만 한번 출력 -> return
        =123 출력

        depth를 false
        `arr =  1100 -> 1101
        visited = false -> true
        depth = 3 -> 2 -> 3 -> 4
        r = 0
        124

        arr = 1101 -> 1100 -> 1000 -> 1010 -> 1011
        visited =
        depth = 4 -> 3 -> 2 -> 1 -> 2 -> 3 -> 4
        r = 0                    -> 2 -> 1 -> 0
         */

        if (r == 0) { //r이 1 씩 감소
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        //출력은 되지 않는 상황 return 되는 경우
        if (depth == n) { //배열에 가장 끝에 도달
            return;
        }

        //재귀 형태로 구현
        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false; //depth가 돌아갈때 false
        combination(arr, visited, depth + 1, n, r);


    }

    public static void main(String[] args) {
//      Test code
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = {false, false, false, false};

        Practice_04 p = new Practice_04();
        p.combination(arr, visited, 0, 4, 3);
    }
}

코드를 보는데 처음 봤을때는 이해하기 힘들었다. 두번째 봤을때는 강의만 쫓다가 내가 스스로 생각을 해보니 이해가 되었다.