[알고리즘] 조합(Combination) (Java)

 

조합이란?

 

n개의 숫자 중에서 r개의 수를 순서 없이 뽑는 경우를 말한다.

 

예를 들어 3개의 숫자(1, 2, 3)에서 2개의 수를 순서 없이 뽑는 경우는 이와 같다.

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

 

조합의 기본 원리

 

조합은 기호로 nCr로 표기한다.

또한 해당 식으로 표현이 가능하다.

nCr = n-1Cr-1 + n-1Cr

즉 조합은 하나의 원소를 선택한 경우 + 하나의 원소를 선택하지 않을 경우, 이 둘의 합으로 나타낸다.

 

예를 들어 (1,2,3)의 수에서 2개의 수를 선택하는 조합을 생각해 보자.

• 1을 선택하는 경우 (하나의 원소를 선택한 경우)
• 1을 선택하지 않는 경우 (하나의 원소를 선택하지 않을 경우)

 

1을 선택하는 경우 

- (1, 2), (1, 3)

1을 선택했으므로 (2, 3) 두 개의 수 중에서 1개의 수를 뽑아야 하므로 2C1, 즉 n-1Cr-1이 된다.

 

1을 선택하지 않는 경우

- (2, 3)

1을 선택하지 않았으므로 (2, 3) 두 개의 수 중에서 2개의 수를 뽑아야 하므로 2C2, 즉 n-1Cr이 된다.

 

해당 식을 바탕으로 결국 더 이상 쪼개지지 않을 때까지 즉, nC0 = 1이 될 때까지 구한다면 nCr을 구할 수 있게 된다!!

 

조합의 경우의 수 구하기

 

nCr에서 n과 r이 같은 경우, 해당 숫자를 모두 뽑는 경우만 존재하므로 경우의 수는 1가지이다.

nCr에서 r이 0인 경우, 숫자를 더 이상 뽑지 않는 선택지만 존재하므로 경우의 수는 1가지이다.

그 외의 경우에는 위에서 다뤘던 nCr = n-1Cr-1 + n-1Cr의 식을 통해요 재귀로 호출한다.

 

public static void main(String[] args) {
    System.out.println(combination(3, 2)); // 3개 중에서 2개를 뽑는 조합의 경우의 수
}

public static int combination(int n, int r) {
    if (n == r || r == 0)
        return 1;
    else
        return combination(n - 1, r - 1) + combination(n - 1, r);
}

 

조합 구하기

 

조합을 구하는 방법은 배열의 처음부터 마지막까지 돌며

 

-  현재 인덱스를 선택하는 경우

-  현재 인덱스를 선택하지 않는 경우

 

이렇게 두 가지의 경우를 완전 탐색해야 한다.

 

해당 조합을 구하는 구현 방법은 총 2가지가 존재한다.

1. 백 트래킹

2. 재귀

 

백트래킹을 이용한 구현

먼저 구현을 위해 필요한 요소들을 살펴보자.

• arr: 조합을 뽑아낼 배열
• n: 배열의 길이
• r: 뽑아야 하는 수
• visited: 해당 수가 뽑혔는지 확인하기 위한 배열

public class Comb1 {
    static int[] arr;
    static boolean[] visited;
    static int n, r;

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

        combination(0, r);
    }
 }

 

이제 combination 함수를 살펴보자.

public static void combination(int start, int r) {
    if (r == 0) {
        print();
    } else {
        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(i + 1, r - 1);
            visited[i] = false;
        }
    }
}

 

start와 r, 2가지 매개변수가 있다.

• start: 배열의 시작 index
• r: 뽑을 숫자의 개수

예를 들어, 3C2를 구한다고 가정해 보자.

arr = {1, 2, 3};
r = 2;

 

동작 과정

 

1. 처음 start와 r은 (0, 2)으로 시작한다.

2. 1을 방문처리한 후 start를 +1, r을 -1 한다.

3. 2를 방문처리한 후 start를 +1, r을 -1 한다.

4. r이 0과 같아져서 해당 조합을 출력한다. => (1, 2)

5. 2의 방문처리를 해제한다.

6. 3을 방문처리한 후 start를 +1, r을 -1 한다.

7. r이 0과 같아져서 해당 조합을 출력한다. => (1, 3)

8. 3의 방문처리를 해제한다.

9. 1의 방문처리를 해제한다.

10. 2를 방문처리한 후 start를 +1, r을 -1 한다.

11. 3을 방문처리한 후 start를 +1, r을 -1 한다.

12. r이 0과 같아져서 해당 조합을 출력한다. => (2, 3) 

13. 3의 방문처리를 해제한다.

14. 2의 방문처리를 해제한다.

 

해당 과정을 통해 (1,2), (1,3), (2,3)을 출력하게 된다.

 

그림을 통해 살펴보면 조금 더 쉽게 이해할 수 있다.

 

전체 코드

 

public class Comb1 {
    static int[] arr;
    static boolean[] visited;
    static int n, r;

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

        combination(0, r);
    }

    public static void combination(int start, int r) {
        if (r == 0) {
            print();
        } else {
            for (int i = start; i < n; i++) {
                visited[i] = true;
                combination(i + 1, r - 1);
                visited[i] = false;
            }
        }
    }

    public static void print() {
        for (int i = 0; i < arr.length; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}

 

r을 depth로 바꾸어 구현이 가능하다.

이때 depth는 뽑은 숫자의 개수이다.

public class Comb1 {
    static int[] arr;
    static boolean[] visited;
    static int n, r;

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

        combination(0, 0);
    }

    public static void combination(int start, int depth) {
        if (depth == r) {
            print();
        } else {
            for (int i = start; i < n; i++) {
                visited[i] = true;
                combination(i + 1, depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void print() {
        for (int i = 0; i < arr.length; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}

 

재귀를 이용한 구현

백트래킹 방법과 달리 이번 구현에서는 depth로 이전에 탐색한 값인지 판단한다.

 

public static void combination(int depth, int r) {
    if (r == 0) {
        print();
        return;
    }
    if (depth != n) {
        visited[depth] = true;
        combination(depth + 1, r - 1);
        visited[depth] = false;
        combination(depth + 1, r);
    }
}

 

depth와 r, 2가지 매개변수가 있다.

• depth: 현재 index
• r: 뽑을 숫자의 개수

depth가 index의 범위를 벗어나지 않는 동안 재귀함수를 수행한다.

• 해당 숫자를 뽑은 경우: combination(depth + 1, r - 1)
• 해당 숫자를 뽑지 못한 경우: combination(depth + 1, r)

두 경우 모두 해당 숫자를 확인했으므로 depth를 1 증가시킨다.

 

r이 0이 되는 경우는 모든 숫자가 뽑힌 경우이므로 해당 조합을 출력한 뒤 재귀를 종료한다.

또한 depth가 n이 되면 모든 인덱스를 모두 확인했으므로 재귀를 종료한다.

 

그림을 살펴보면 조금 더 쉽게 이해할 수 있다.

 

전체 코드

 

public class Comb2 {
    static int[] arr;
    static boolean[] visited;
    static int n, r;

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

        combination(0, r);
    }

    public static void combination(int depth, int r) {
        if (r == 0) {
            print();
            return;
        }
        if (depth != n) {
            visited[depth] = true;
            combination(depth + 1, r - 1);
            visited[depth] = false;
            combination(depth + 1, r);
        }
    }


    public static void print() {
        for (int i = 0; i < arr.length; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}

 

 

 

Reference

https://minhamina.tistory.com/38