Combination(조합)

>>>>>>> 소스코드.git

조합이란?

n개의 값 중에서 r개의 숫자를 순서를 고려하지 않고 나열한 경우의 수이다.

 

예를 들어서 [1, 2, 3] 배열에서 2개의 수로 만들어지는 경우의 수를 구하라고 하면

[1, 2]
[1, 3]
[2, 3]

이렇게 나온다.

순열에에서 나오는 [2, 1], [3, 1], [3, 2]는 중복되므로 제외 대상이다.

 

구현하는 방법은 여러가지가 있겠지만, 여기서 핵심은 주어진 배열의 처음부터 끝까지 순회하면서 해당 인덱스의 값을 선택했을 경우 / 선택하지 않았을 경우 이렇게 두 가지로 나눠 모든 경우를 탐색하는 완전 탐색을 해주면 된다.

 

소스 코드

검색해보니 제일 잘 나와있는 대표적인 구현 방법 두 가지를 설명할 것이다.

1. 백트래킹을 이용한 구현

private void combination(int[] arr, boolean[] visited, int start, int n, int r) {
    if (r == 0) {
        print(arr, visited, n);
        return;
    }

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

백트래킹이란?

검색해보니 제일 이해하기 쉬운 설명은 깊이 우선 탐색(Depth First Search, DFS)으로 답을 찾다가 조건에 맞지 않으면 더 깊이 탐색하지 않고 이전으로 돌아와서 다른 경우의 수를 들여다 보는 것이라고 할 수 있다. 

 

소스코드 설명

start 인덱스를 기준으로 start보다 작으면 후보에서 제외한다.

visited 배열의 r크기 인덱스만큼 true가 되고서 시작한다.

r = 0이 되면 해당 경우의 수를 출력하고 return을 하고, 이전 반복문에서 해당 인덱스는 다시 false로 바뀐다. 그 다음 인덱스가 true로 바뀌면서 그 다음 경우의 수를 출력한다.

 

말로는 잘 이해가 되지 않을 것이다. 메서드를 호출할 때 Stack 개념을 잘 이해하고 있고, 직접 그림을 그리면서 한 번 실행해보면 이해가 된다. 나도 그림 그리면서 이해함... (그림은 생략)

 

 

2. 재귀 함수를 이용한 구현

private void comb(int[] arr, boolean[] visited, int depth, int n, int r) {
    if (r == 0) {
        print(arr, visited, n);
        return;
    }

    if (depth == n) {
        return;
    }

    visited[depth] = true;
    comb(arr, visited, depth + 1, n, r - 1);

    visited[depth] = false;
    comb(arr, visited, depth + 1, n, r);
}

재귀 함수는 depth 변수를 사용한다. 현재 인덱스라고 생각하면 편하다. 중복이 허용이 안되기 때문에 재귀 호출 때 이전 인덱스를 안봐도 되기 때문에 depth+1만 해주면 되고, depth == n 이 되면 배열의 모든 인덱스를 다 봤기 때문에 return하여 종료한다.

 

---

private void print(int[] arr, boolean[] visited, int n) {
    for (int i = 0; i < n; i++) {
        if (visited[i]) {
            System.out.print(arr[i] + " ");
        }
    }
    System.out.println();
}

위 소스 코드는 해당 경우의 수를 출력하는 print 메서드이다.