[알고리즘] 순열과 조합

코딩테스트에서 자주 만났던 순열과 조합에대해 정리해보려고 합니다!

 

순서, 중복여부에 따라서 순열, 조합, 중복순열, 중복조합으로 나뉜다.

종류	순열	중복순열	조합	중복조합
순서 다름 구분 여부	O	O	X	X
중복 여부	X	O	X	O
{1, 2, 3}, r = 2일 경우	1 2  1 3  2 1  2 3  3 1  3 2	1 1  1 2  1 3  2 1  2 2  2 3  3 1  3 2  3 3	1 2  1 3  2 3	1 1  1 2  1 3  2 1  2 2  2 3  3 1  3 2  3 3
특징	원소저장 배열 result 필요 방문처리 배열 visited 필요 탐색 시작기준 start 필요X	원소저장 배열 result 필요 방문처리 배열 visited 필요X 탐색 시작기준 start 필요X	원소저장 배열 result 필요X 방문처리 배열 visited 필요 탐색 시작기준 start 필요	원소저장 배열 result 필요 방문처리 배열 visited 필요X 탐색 시작기준 start 필요

[특징 비교 정리]

원소저장 배열 result -> 조합을 뺀 나머지 순열/중복순열/중복조합에서 필요

방문처리 배열 visited -> 중복허용이 안되는 순열/조합에서 필요

탐색 시작기준 start  -> 순서가 달라도 같은것으로 보는 조합/중복조합만 필요

depth, r -> 모두 필요

 

1. 순열 - Permutation

서로 다른 n개에서 r개를 뽑아 "정렬"하는 경우의 수 -> 순서O, 중복X

ex) {1, 2}이 주어질 때 순열에서는 순서만 다른 [1, 2]와 [2, 1]을 다른 것으로 인식한다.

 

JAVA 코드로 순열 코드를 짜면 다음과 같다.

public class 순열 {
    public static void permutation(int[] arr, int[] result, boolean[] visited, int depth, int r){
        // 순열 출력
        if(depth == r){
            for(int num : result){
                System.out.print(num);
                System.out.print(" ");
            }
            System.out.println();
            return;
        }
        for(int i = 0; i < arr.length; i++){
            if(!visited[i]){
                // 방문처리
                visited[i] = true;
                result[depth] = arr[i]; // 값 넣기
                permutation(arr, result, visited, depth+1, r); // 재귀
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        int[] result = new int[r];
        boolean[] visited = new boolean[arr.length];

        permutation(arr, result, visited, 0, r);
    }
}

- result: 순서대로 방문하는 원소를 저장하는 배열

- 중복이 불가능하기 때문에 visited를 이용해서 이미 선택한 원소를 다시 선택하지 않도록 해준다.

 

 

2. 중복순열

서로 다른 n개에서 "중복이 가능"하게 r개를 뽑아 정렬하는 경우의 수 -> 순서O, 중복O

 

JAVA 코드로 중복순열 코드를 짜면 다음과 같다.

public class 중복순열 {
    public static void permutation(int[] arr, int[] result, int depth, int r){
        // 중복순열 출력
        if(depth == r){
            for(int num : result){
                System.out.print(num);
                System.out.print(" ");
            }
            System.out.println();
            return;
        }

        for(int i = 0; i < arr.length; i++){
            result[depth] = arr[i];
            // 중복허용이므로 방문체크 불필요
            permutation(arr, result, depth+1, r);
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int r = 2;
        int[] result = new int[r];
        permutation(arr, result, 0, r);
    }
}

- 순열과 유일한 차이는 중복이 가능하다는 것이다. 따라서 순열코드에서 중복을 방지하기 위해 사용했던 visited가 필요없다.

 

 

3. 조합 - Combination

서로 다른 n개에서 "순서 없이" r개를 뽑는 경우의 수 -> 순서X, 중복X

 

ex) {1, 2}이 주어질 때 조합에서는 순서가 다른 [1, 2]와 [2, 1]을 같은 것으로 인식한다.

 

JAVA 코드로 조합 코드를 짜면 다음과 같다.

    public static void combination(int[] arr, boolean[]  visited, int start, int depth, int r){
        if(depth == r){
            for(int i = 0; i < arr.length; i++) {
                if (visited[i]) {
                    System.out.print(arr[i]);
                    System.out.print(" ");
                }
            }
                System.out.println();
                return;
        }

        for(int i = start; i < arr.length; i++){
            if(!visited[i]){
                visited[i] = true; // 방문체크
                combination(arr, visited, i+1, depth+1, r);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int r= 2;
        boolean[] visited = new boolean[arr.length];
        combination(arr, visited, 0, 0, r);
    }

- 순서가 상관없고 중복을 허용하지 않기 때문에, 탐색의 시작 기준을 start로 하고 visited를 이용하여 중복여부를 확인한다.

- 재귀 호출 시 start와 depth 모두 +1 해준다.

 

 

4. 중복조합

서로 다른 n개에서 순서 없이, "중복 가능"하게 r개를 뽑는 경우의 수 -> 순서X, 중복O

 

JAVA 코드로 중복조합 코드를 짜면 다음과 같다.

public class 중복조합 {
    public static void combination(int[] arr, int[] result, int start, int depth, int r){
        // 중복조합 출력
        if(depth == r){
            for(int num : result){
                System.out.print(num);
                System.out.print(" ");
            }
            System.out.println();
            return;
        }

        for(int i = 0; i < arr.length; i++){
            result[depth] = arr[i];
            combination(arr, result, i, depth+1, r);
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int r = 2;
        int[] result = new int[r];
        combination(arr, result, 0, 0, r);
    }
}

- 조합과 유일한 차이는 중복이 가능한 것이므로 visited가 불필요하다.

- 현재 사용한 원소보다 뒤의 것만 선택가능한 것이 아니라, 현재 원소를 포함하여 그 뒤의 것들까지 선택가능하므로 재귀 호출에서 start를 i+1로 넘기던 것을 그냥 i로 넘기면 된다.

 

 

이제 코테에서 순열,조합 나오면 잘 풀 수 있겠지!?