조합과 순열

코딩 테스트 시 필요한 이유

필자는 Brute Force 방식으로 코테를 푸는 것에 대한 거부감이 있었다.

말이 좋아 Brute Force 방식이지 가볍게 말하면 일일이 세보자라는 알고리즘이고 대기업들은 코테로 이런 단순한 알고리즘 문제를 내지는 않을 것이라 생각했기 때문이다.

 

하지만 프로그래머스에 있는 코딩 테스트 문제를 풀어보며 생각보다 Brute Force 방식으로 풀어도 되는 문제들이 많았다.

특히 Lv2 같은 쉬운 문제들은 대부분 Brute Force 방식을 사용하고 있었다.

 

이렇다보니 대기업도 Brute Force 방식으로 문제를 풀도록 하는 경우가 있구나라는 생각으로 바뀌었다.

 

개인적으로 Brute Force 방식 중 가장 까다로웠던 것이 "조합과 순열"을 구현하는 것이었다. 원래는 이런 Brute Force 문제는 별로 중요하지 않다 생각했지만 이 생각이 바뀐 만큼 나를 까다롭게 했던 "조합과 순열"에 대한 알고리즘도 한 번 정리하고 가야겠다고 생각했다.

 

Java로 조합 및 순열을 구하는 방법을 알기 전 조합과 순열이 무엇인지 간단히 정리하고 가자.

• 조합 : "순서와 관계 없이" n개의 수 중 r개의 수를 뽑는 경우
• 순열 : "순서를 고려하며" n개의 수 중 r개의 수를 뽑는 경우

---

조합

◎ 아이디어

조합의 가장 중요한 객체는 "boolean[] visit"으로써 조합에 뽑혔는지 체크하는 Boolean 배열이다.

 

visit[i] = true일 경우 arr[i] 값이 조합에 뽑혔다는 의미이고 visit[i] = false인 경우 arr[i] 값이 조합에 뽑히지 않았다는 것이다.

이런 개념과 백트래킹을 활용하여 조합을 구할 수 있는 것이다.

 

그렇다면 구체적으로 조합을 알고리즘을 파보자.

 

◎ 순서

0. combination(int[] arr, boolean[] visit, int start, int n, int r)

• arr : 조합을 만들 수를 저장한 배열
• visit : arr[i]를 조합에 포함하는지 아닌지를 판단하는 배열
• start : arr[0] ~ arr[start-1]까지는 조합에 포함시킬지 여부를 판단한 상태로 arr[start] ~ arr[n-1] 중 어떤 값을 조합에 포함시킬지 판단해야 함
• n : nCr의 n. arr 배열의 길이와 동일
• r : nCr의 r. 조합의 길이

 

1. combination(arr, new boolean[arr.length], 0, arr.length, r)

재귀함수를 호출하는 단계이다.

 

arr는 이미 주어진 배열이므로 그대로 전달해줘도 된다.

 

boolean[] visit 같은 경우 arr[i]가 조합에 포함되어 있는지 판단하기 위한 배열로써 길이는 arr와 동일해야 한다.

 

우리는 arr[0] ~ arr[n-1] 값으로 조합을 만들고 싶기 때문에 start = 0이다.

 

r은 이미 주어졌을 것이고 위에서 말했듯 n은 arr 길이와 동일하다.

 

2. 재귀함수 중 r!=0인 경우

r이 0이 아니라는 의미는 아직 조합에 r개의 원소가 포함되지 않았음을 의미한다.

따라서 r=0이 될 때까지 조합에 원소를 더 담아줘야 한다.

 

먼저 우리는 arr[start] ~ arr[n-1] 중 값을 선택하여 조합에 포함시킬 것이다.

따라서 for(int i =start;i<n;i++)문을 통해 조합에 포함시킬지 여부를 판단한다.

 

arr[i]를 조합에 포함시킨다고 가정하자. 그렇다면 visit[i] = true가 돼야 할 것이다.

우리는 arr[0] ~ arr[i] 중 어떤 값을 조합에 포함시킬지 판단했으므로 start = i +1이 될 것이며 arr[i] 값을 포함시켰으므로 r-1을 다음 재귀함수에 전달해줘야 할 것이다.

재귀함수가 종료되면 visit[i] = false를 통해 arr[i]를 포함시키지 않는 조합을 찾아야 한다.

 

3. 재귀함수 중 r = 0인 경우

r이 0이라는 의미는 조합에 r개의 원소를 뽑았다는 의미이다.

즉 visit[i] = true인 i를 찾아 arr[i]를 출력하면 조합에 포함된 원소 값을  출력할 수 있는 것이다.

 

◎ 코드

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

    for(int i = start; i < n; i++){
        visit[i] = true;
        combination(arr, visit, i + 1, n, r - 1);
        visit[i] = false;
    }
}

public static void main(String[] args) throws Exception {

    int[] arr = new int[]{1,2,3,4};

    for(int i =1;i<=arr.length;i++) {
        System.out.println("[4개 원소 중 " + i + "개를 뽑는 경우]");
        combination(arr, new boolean[arr.length], 0, arr.length, i);
    }

}

 

참고로 위 코드는 Github Copilot이 자동으로 짜준 코드인데 코드 완성도가 높아서 생각보다 놀랐다. MVC 패턴에서는 그렇게 좋아 보이진 않았는데 단순 로직을 구현할 때는 Copilot 괜찮은 것 같다. 활용도를 늘려볼 생각을 해야겠다.

---

중복 조합

조합은 한 번 뽑은 수는 더 이상 뽑을 수 없다.

하지만 한 번 뽑은 수를 또 뽑을 수 있는 "중복 조합"의 경우는 어떤 알고리즘으로 짜야 하는지 호기심이 생겼다.

분명 조합과는 약간 다르겠지만 큰 차이는 없다고 생각했기 때문이다.

 

결론부터 말하자면 boolean[] visit이 아닌 int[] visitNum을 사용하면 된다.

조합은 visit[i] = true일 경우 이후 arr [i]는 포함시킬 수 없으므로 i번째 값은 더 이상 볼 필요가 없기 때문에 2가지 상태만 존재하는 boolean [] visit 사용이 가능했다.

하지만 중복 조합은 visit[i] = true여도 그 값을 또 사용할 수 있다.

따라서 "몇 번 사용했는지"를 확인하기 위한 int[] visitNum을 사용하면 된다.

또한 visit[i] = true라면 arr[i+1]부터 확인하면 되는 조합과는 달리 arr[i]를 조합에 중복 포함시킬 수 있으므로 start+1이 아닌 start를 다음 재귀함수로 넘겨줘야 한다.

 

◎ 코드

public static void dupCombination(int[] arr, int[] visit, int start, int n, int r){
    if(r == 0){
        for(int i = 0; i < n; i++){
            for(int j=0;j<visit[i];j++){
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
        return;
    }

    for(int i = start; i < n; i++){
        visit[i]++;
        dupCombination(arr, visit, i, n, r - 1);
        visit[i]--;
    }
}

public static void main(String[] args) throws Exception {

    int[] arr = new int[]{1,2,3};

    for(int i =1;i<=arr.length;i++) {
        System.out.println("[중복을 허용하며 3개 원소 중 " + i + "개를 뽑는 경우]");
        dupCombination(arr, new int[arr.length], 0, arr.length, i);
    }

}

---

순열

순열의 경우 조합보다는 조금 까다로운게 바로 "순서"를 신경 써야 한다는 것이다.

따라서 방문 여부를 확인해주는 boolean[] visit 뿐만이 아닌 "몇 번째로 뽑혔는지"를 저장하는 int[] value 배열 또한 필요하다.

 

먼저 "start"는 필요 없다. 왜냐하면 순서를 신경쓰기 때문에 {arr[2], arr[1]}과 {arr[1], arr[2]}는 다르므로 현재 index가 어디든 무조건 arr[0] ~ arr[n-1]까지 원소를 조회해봐야 한다.

 

두 번째로 순열 결과를 출력할 때 visit[i]를 사용하지 않는다는 것이다.

visit[i]는 단순히 "그 값을 순열에 포함시켰는지 아닌지"를 판단하기 때문에 순서가 중요한 순열 값을 출력할 때는 아무런 힘도 발휘하지 못한다.

visit은 단순히 순열에 값을 포함시킬 때 그 순열에 arr[i]가 이미 포함되어 있는지 아닌지만 판단하는 역할을 수행하는 것이다.

 

대신 value 배열에 순서대로 값을 저장하고 value[0] ~ value[depth-1]까지 출력하면 된다.

 

◎ 코드

public static void permutation(int[] arr, boolean[] visit, int[] value, int n, int r, int depth) {
    if(r==0){
        for(int i =0;i<depth;i++){
            System.out.print(value[i]+" ");
        }
        System.out.println();
        return;
    }

    for(int i =0;i<n;i++){
        if(!visit[i]){
            visit[i] = true;
            value[depth] = arr[i];
            permutation(arr, visit, value, n, r-1, depth+1);
            visit[i] = false;
        }
    }
}

public static void main(String[] args) throws Exception {

    int[] arr = new int[]{1,2,3};

    for(int i =1;i<=arr.length;i++) {
        System.out.println("[3개 원소 중 "+ i + "개 원소로 순열을 만들기]");
        permutation(arr, new boolean[arr.length], new int[arr.length], arr.length, i, 0);
    }

}