[알고리즘] 순열, 중복순열, 조합, 중복조합 총정리 !

코딩테스트를 준비하면서 알고리즘 문제풀이를 하고, 또 실제로 코딩테스트를 치면서 자주 만나는 유형의 문제가 바로 순열, 조합입니다 ! ( 당장 지난 주말 코테에서도 두 번 다 마주친 .. )

이제 순서를 신경 써야하는가 ? 중복이 가능한가 ? 에 따라서 순열, 조합, 중복 순열, 중복 조합중에 잘 판단을 해서 문제에 적용을 하면 되는데요 !

그래서 오늘은 순열, 중복 순열, 조합, 중복 조합 모두를 한 번 정리해보려 합니다 !!! 레츠꼬.. 🔥

순열 - Permutation

서로 다른 n개에서 r개를 뽑아서 정렬하는 경우의 수

자 이제 순열, 조합, 중복 순열, 중복 조합 모두가 n개에서 r개를 뽑는다는 것은 동일합니다. 순열의 정의에서 '정렬'이라는 단어가 순열의 특징을 나타내는데, 바로 순서가 있다는 겁니다.

• 예를 들어서 살펴보면 [1,2]와 [2,1]은 순서가 다르기 때문에, 순열에서는 다른 것으로 카운팅 한다는 것 !

이제 Java로 순열 코드를 어떻게 작성하면 좋을지 살펴봅시다 !

public class AlgorithmStudy {
    public static void permutation(int[] arr, int[] out, boolean[] visited, int depth, int r){
        if(depth == r){
            for(int num: out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=0; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, out, visited, depth+1, r);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], new boolean[arr.length], 0, r);
    }
}

• 순서를 신경쓰는 순열이기 때문에, index상으로 뒤에있는 원소가 더 앞에 오는 경우도 카운팅을 해야합니다. 예시로 언급한 [2,1]과 같은 경우죠 ! 따라서 탐색을 수행하는 반복문은 0부터 탐색을 시작해야합니다.
• 또한 순서를 신경쓰는 순열이기 때문에, 순서대로 방문 원소를 저장해야 하므로 선택된 원소를 순서대로 저장할 배열 out을 사용합니다.
• 중복해서 선택하는 것은 불가능하기 때문에 visited를 이용해서 이미 선택한 원소를 다시 선택하지 않도록 해줍니다.

중복 순열

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

• 순서가 있게 뽑는 순열과 동일하지만, 같은 원소를 중복해서 뽑을 수 있다는 차이만 있습니다.

이제 이 점을 고려해서 Java로 어떻게 구현하면 좋을지 살펴봅시다 !

public class AlgorithmStudy {
    public static void permutation(int[] arr, int[] out, int depth, int r){
        if(depth == r){
            for(int num: out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=0; i<arr.length; i++){
            out[depth] = arr[i];
            permutation(arr, out, depth+1, r);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], 0, r);
    }
}

• 순열과 유일한 차이가 중복이 가능하다는 것이므로, 순열 코드에서 중복을 방지하기 위해서 사용했던 visited부분을 제거해주면 됩니다.

조합 - Combination

서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

• 순서와 상관 없다는 말은 순열과 다르게 [1,2]와 [2,1]을 같은 것으로 취급한다는 것입니다.

그럼 이와 같은 특징을 고려하여 Java로 어떻게 작성하면 좋을지 살펴봅시다 !

public class AlgorithmStudy {
    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.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;
        combination(arr, new boolean[arr.length], 0, 0, r);
    }
}

• 순서가 상관이 없어 [1,2]와 [2,1]가 같다고 했기 때문에 이런 경우 [1,2]만을 카운팅 해줍니다. 그러기 위해서 현재 선택한 원소보다 뒤에 있는 원소에 대해서만 탐색을 진행해줍니다. 이를 코드로 구현하기 위해서 탐색의 시작 index를 의미하는 start 원소를 사용해주었습니다. 탐색의 시작 기준을 start로 해주고, 재귀 호출을 할 때에는 현재 index인 i에 1을 더한 값을 start로 넣어주었습니다.
• 추가적인 특징으로는 순서가 상관이 없고, 중복도 없으므로 선택된 원소를 따로 저장하지 않고, 원소들과 visited만 이용하여 방문한 원소들을 순서대로 확인하면 곧 선택된 조합입니다.

중복 조합

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

• 순서 없이 뽑는 조합과 동일하지만, 이미 뽑은 것을 또 뽑을 수 있다는, 즉 중복이 가능하다는 차이점이 있습니다.

이제 이 특징을 고려하여 Java로 어떻게 구현하면 되는지 살펴봅시다 !

public class AlgorithmStudy {
    public static void combination(int[] arr, int[] out, int start, int depth, int r){
        if(depth == r){
            for(int num : out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            out[depth] = arr[i];
            combination(arr, out, i, depth+1, r);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new int[r], 0, 0, r);
    }
}

• 조합과 유일한 차이점은 중복이 가능하다는 것이므로, 조합 코드에서 중복을 체크하기 위해 사용한 visited를 사용하는 부분을 제거해주면 됩니다.
• 또한 현재 선택한 원소보다 뒤의 것만 선택 가능하지 않고, 현재 선택한 원소를 포함하여 그 뒤의 것들을 선택 가능한 것이므로 재귀 호출에서 start로 i+1을 넘기던 조합 코드에서 그냥 i를 넘기는 것으로 수정해주면 됩니다.
• 조합과는 다르게 중복이 가능하기 때문에 선택한 원소를 저장하는 배열은 필요합니다 !

이렇게 순열과 조합 총정리를 해봤습니다 ! 헷갈리지 않고, 고민하지 않고 이제 코테에서 완탐 문제는 바로바로 해결해봅시다 !