🖤 알고리즘 이론 - 순열과 조합 [JAVA]

 

0. 설명 하려는 것

(1) 순열, 조합, 중복 순열, 중복 조합의 정의

(2) JAVA 언어를 썼을 때, 구현 방법

1. 순열

(1) 순열의 뜻

nPr = n 개 중에서 r개를 중복 없이 뽑아서 순서 있게 나열하는 것을 말한다. 따라서 {1, 2, 3, 4, 5} 중 5P3 에서 {1, 2, 3} 과 {1, 3, 2}는 다른 숫자이다.

(2) 구현 방법

순열은 재귀로 구현한다. 순열을 재귀로 구현하기 위해서는 다음과 같은 구성요소들이 필요하다.

1. 전체 원소들에 대한 방문 배열 isVisited [] : 순열로 값을 뽑을 때, 중복이 없어야 하므로, 방문 배열을 통해, 이미 방문한 지점은 그냥 지나치도록 구현 해야 한다.
2. 뽑힌 r개의 원소를 담을 배열 output [] : 전체 원소가 담긴 배열을 arr 이라 했을 때, 뽑힌 원소만 담을 배열 output 또한 필요하다.
3. depth 변수 : 재귀가 몇 번째 깊이인지 나타내는 변수이다. 해당 변수가 바로 output 배열의 원소를 대입해야할 위치이다.
4. 기저 조건 : output을 nPr 중 r의 크기를 넘어섰을 경우, (depth가 r일 경우), 더 이상, 원소를 n개 중에 고르는 연산을 그만하고, 문제에서 원하는 연산을 하도록 하는 기저 조건이 필요하다. 기저 조건 수행 후에는 이전 재귀로 돌아가야 한다. 따라서 맨 마지막에 return을 써줘야 한다.

방법은 다음과 같다.

1. depth < r 일 때,
   1. arr[i]가 미방문한 지점일 경우, arr[i]를 방문으로 체크한다. output[depth] = arr[i]를 집어넣고, depth+1 의 재귀로 들어간다.
   2. arr[i]가 방문한 지점일 경우, for 문을 통해 arr[i+1]이 미방문인지 방문인지 확인한다.
   3. (i)번의 재귀가 끝나고 반환 되었을 경우, output[depth] = arr[i] 인 경우의 수는 다 본 것이다. 이제 for 문을 돌려서 output[depth] = arr[i+1]인 경우를 확인한다.
2. depth == r 일 떄,
   1. 지금까지 뽑은 수들은 nPr을 충족했다. 해당 값들로 문제가 원하는 연산을 한다.

(3) 코드분석

    // ⭐ 1번: 순열

        // 순열이란? : nPr = n 개 중 r개를 중복 없이 뽑아서 순서를 고려하여 나열 하는 것
        // 순서를 고려한다. => 1 3 2 와 1 2 3은 서로 다른 경우의 수이다.

    /*  1. arr[]    : 원본 배열
    *   2. output[] : 출력하고자 하는 배열
    *   3. visited[]: 방문 여부 체크
    *   4. depth    : 현재까지 뽑은 수의 개수
    *   5. r        : 총 뽑아야 하는 수의 개수
    */
    public static void permutation(int [] arr, int [] output, boolean [] visited, int depth, int r) {

        // 1. 기저 조건 (depth 가 r 이 되면, 값을 전부 뽑아서 일렬로 나열한 것이므로, 문제에서 원하는 행동을 행한다.)
        // 0부터 셌기 때문에 depth == r이란 소리는 모두 세고 +1 해서 원래 세야할 수를 넘어섰다는 뜻이다.
        // 따라서 여기서는 원래 행하던 'N개 중 r 뽑아서 일렬로 나열' 계산을 하지 않고, 조건 충족 시 해야할 계산을 행한다.
        if(depth == r){
            for(int temp: output){

                if(temp == 0) {
                    continue;
                }

                System.out.print(temp + " ");
            }
            System.out.println();

            // 1-1) 다른 경우의 수를 둘러보기 위해 이전 재귀로 돌아간다.
            return;
        }

        // 2. nPr 실행
        for (int i = 0; i < arr.length; i++) {

            // 중복이 없어야 하므로, 방문 했으면 고려하지 않고 다음으로 넘어간다.
            if(!visited[i]){
                visited[i] = true;
                // nPr의 현재 자리 수 = 방문하지 않은 값을 넣음
                output[depth] = arr[i];
                // 다음 수를 세러 넘어간다.
                permutation(arr,output,visited, depth+1, r);

                // output[1] = 1, output[2] = 5 라고 하고 , 현 depth = 2, i = 5 라고 하자.
                // 재귀를 끝내고 돌아왔다는 것은 {1,5, ...} 의 모든 경우를 보고 왔다는 것이다.
                // 따라서 i = 5는 다른 위치에서 경우의 수를 셀 때 필요하므로, 미방문으로 전환한다.
                visited[i] = false;
            }

            // 이제 loop가 다음으로 넘어갈 것이고, depth = 2에서 i = 6인 모든 경우의 수를 볼 것이다.
        }
    }

2. 조합

(1) 조합의 정의

nCr이란 n개 중에서 r개를 뽑는 경우의 수이다. 순열과의 차이점은 nCr의 경우, 순서를 고려하지 않는다는 점이다.

(2) 구현 방법

순열과 다르게 인수로 start 변수를 둔다. **start 변수**는 해당 index 지점부터 숫자를 고르도록 하는 변수이다. 해당 변수가 필요한 이유는 다음과 같다. {1, 2, 3, 4, 5}에서, 5C3을 구해보자. 만약 1부터 시작하여 3개를 골랐을 경우, 1,2,3 1,2,4 .... 1,4,5 정도가 될 것이다. 다음 2부터 시작하여 3개를 골라보자. 2,1,3 이 가능한 숫자인가? 아니다. 왜냐하면 1을 셀 때 셌기 때문이다. 이처럼, **1부터 시작하여 그보다 큰 수 중에 남은 2개를 고르는 경우의 수가 이미 1과 2 를 골랐을 떄 나올 수 있는 모든 경우의 수를 포함하고 있다!** 따라서, 2부터 셀 때는 1을 고려하지 말고 2보다 큰 3부터 끝까지의 수를 고르면 된다. 이는 3부터 시작할 때, 4부터 시작할 때, 5부터 시작할 때, 모두 같다.

(3) 코드 분석

  // ⭐ 2번: 조합
    /*
    *   1) 순열과 다른 점
    *   순열과 다르게, 조합은 start 변수를 둔다.
    *   start 변수는 조합에 포함할 값을 찾는 행위를 시작해야할 지점이다.
    *
    *   왜 이런가?
    *   조합은 순서를 고려하지 않는다.
    *   예를 들어 {1,2,3,4,5,6}의 배열에 관하여 6C3을 구한다고 하자.
    *   처음 1을 포함하여 3개를 고르는 수에서 2를 포함하는 모든 경우의 수, 3을 포함하는 모든 경우의 수를 다 구했다.
    *   따라서 그 후 2를 포함하여 3개 고르는 수에서 1을 포함하는 경우는 이미 전에 모두 계산했기에 포함할 필요가 없다.
    *
    *   arr     = 총 배열,       output = 총 배열에서 r 개 중복없이 선택한 수가 들어있는 배열
    *   start   = 선택의 시작점   depth  = 지금까지 선택한 수의 개수
    *   r       = 총 선택해야할 수의 개수
    * */
    public static void Combination (int [] arr, int [] output, int start, int depth, int r ) {

        // 1) 기저 조건
        if(depth == r){
            for(int temp: output){
                if (temp == 0) {
                    continue;
                }
                System.out.print(temp + " ");
            }
                System.out.println();
                return;
        }

        // 2) nCr 계산
        for (int i = start; i < arr.length; i++) {
            output[depth] = arr[i];
            Combination(arr,output,i+1, depth+1, r);
        }
    }

3. 중복 순열

(1) 정의

n개 중에 중복이 가능한 r개를 뽑아서 순서 있게 나열하는 것을 말한다.

(2) 구현 방법

순열을 구현할 때, 방문 배열이 왜 필요 했는가? 이유는, 중복을 제거하기 위함이었다. 이제 중복이 허용되므로 해당 방문 배열이 필요 없어졌다. 따라서 구현은 다음과 같다.

1. depth < r 일 때, 방문 했는지 여부 상관 없이 output[depth] = arr[i]를 집어넣는다. 어짜피 1,1,1,1,1 이 되면 1로만 할 수 있는 모든 경우의 수를 봤으므로, 제일 깊숙한 depth의 for 문이 다음 값으로 넘어간다. 따라서 1,1,1,1,2 가 된다.
2. depth == r 일 때, 이제 문제에서 원하는 일을 하면 된다.

(3) 코드 분석

    // ⭐ 3번: 중복 순열
    /*
    *  1) 순열과의 차이점:
    *   방문 배열이 더 이상 필요 없다. -> 같은 수도 세어서 순서를 고려하여 나열하면 된다.
    *   같은 수 세는 경우 다 세면 for 문이 자동으로 그 다음 수를 고려 할 것이다.
    *   예를 들어 5ㅠ5 를 구하는 경우,
    *   1,1,1,1,1 다 세면 자동으로 5번째 depth의 포문이 자동으로 2로 넘어가서
    *   1,1,1,1,2 가 세어진다. 이것을 이용하면 된다.
    *
    *
    *  arr      = 타겟 배열,            output     = 중복 순열 세면서 담은 값들(모든 경우의 수가 담긴다.)
    *  depth    = 현재까지 뽑은 수의 개수 r          = 총 뽑아야 할 개수
    * */

    public static void RepeatablePermutation (int [] arr, int [] output, int depth, int r ) {
        // 1) 기저 조건
        if(depth == r) {
            for(int temp : output){
                if(temp == 0) {continue;}
                System.out.print( temp + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            output[depth] = arr[i];
            RepeatablePermutation(arr,output,depth+1, r);
        }
    }

4. 중복 조합

(1) 정의

중복이 가능하게 n개 중 r개를 뽑는 경우의 수

(2) 구현 방법

n개 중 중복 되게 r개를 뽑으면 된다. 위의 조합에서 보면 다음 재귀로 갈 때, start 인수에는 i+1이란 값을 집어넣었다. 그 이유는 같은 값부터 시작하는 경우의 수를 제거하기 위함이었다. 근데 이제 다음 depth에서도 같은 값부터 시작해도 된다. 왜냐하면 중복이 허용되기 때문이다. 따라서 코드는 다음과 같다.

(3) 코드 분석

// ⭐ 4번: 중복 조합
    //  조합과 다른 점: 자기 자신도 선택할 수 있으므로, start를 i+1이 아닌 i 자체로 다음 재귀에 넘겨준다.
    
    public static void RepeatableCombination (int [] arr, int [] output, int start, int depth, int r) {
        // 1) 기저 조건
        if(depth == r) {
            for (int temp : output){
                if(temp == 0) {continue;}
                System.out.print(temp + " ");
            }

            System.out.println();
            return;
        }

        for (int i = start; i < arr.length; i++) {
            output[depth] = arr[i];
            RepeatableCombination(arr,output,i,depth+1, r);
        }
    }