[JAVA] JAVA에서 조합 (Combination)

참고 자료

[Java] 조합 Combination

 

조합

n개의 원소 중에서 r개를 순서 없이 뽑는 경우의 수 ( nCr )

조합 수식

하나의 원소를 선택할 경우의 수와 하나의 원소를 선택하지 않을 경우의 수의 합으로 나타낼 수 있다.

하나의 원소를 선택하는 경우 : n개의 원소 중에서 1개를 꼭 뽑는다고 생각하고 r-1개를 채우는 경우

하나의 원소를 선택하지 않을 경우 : n개의 원소 중에서 1개를 꼭 뽑지 않는다고 생각하고 r개를 채우는 경우

 

예를 들어 {1, 2, 3} 원소를 가진 A 집합에서 2개의 숫자를 순서 없이 뽑는다고 하자.

3개에서 2개의 숫자를 뽑는 것과 같다.

위의 가정대로, 숫자 1을 꼭 뽑는다고 가정하고 r-1개 (1개)를 채우는 경우는 {1, 2}, {1, 3} / 2C1 / 2가지 경우

숫자 1을 꼭 뽑지 않는다고 가정하고 r개 (2개)를 채우는 경우 {2, 3} / 2C2 / 1가지 경우

두 경우의 합 3가지로, {1, 2}, {1, 3}, {2, 3} / 3C2 / 3가지의 결과를 얻을 수 있다.

 

이러한 성질을 이용해 조합을 코드로 구현할 수 있다.

 

조합으로 경우의 수 구하기

먼저, nCr 에서 r이 n이거나 0인 경우는 1이다.

그리고, 다른 경우는  n-1Cr-1 + n-1Cr 이기에 재귀를 이용해 구현했다.

import java.util.*;

class Main {

    public static int comb (int[] arr, int n, int r) {
        if (r == 0 || n == r) {
            return 1;
        } else {
            return comb(arr, n-1, r-1) + comb(arr, n-1, r);
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(comb(arr, 3, 2));
    }
}

조합 출력하기

배열을 처음부터 마지막까지 돌면서 현재 인덱스의 원소를 선택하는 경우, 선택하지 않는 경우를 완전 탐색한다.

import java.util.*;

class Main {

    public static void comb (int[] arr, boolean[] visited, int index, int r) {
        if (r == 0) {
            for (int i = 0; i < arr.length; i++) {
                if (visited[i] == true) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }
        if (index == arr.length) {
            return;
        } else {
            visited[index] = true; // 선택하는 경우
            comb(arr, visited, index+1, r-1);

            visited[index] = false; // 선택하지 않는 경우
            comb(arr, visited, index+1, r);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        boolean[] visited = new boolean[arr.length];
        
        int r = 2; // 몇 개 뽑을건지
        comb(arr, visited, 0, r);

    }
}

재귀적으로 구현한다.

배열의 원소를 하나 하나 확인하면서 선택하고 r-1개를 찾는 경우, 선택하지 않고 r개를 찾는 경우를 재귀로 구현한다.

출력되는 조건은 더 이상 선택할 것이 없을 때 (r == 0) 출력한다.

visited에는 선택되었는지 boolean 타입으로 저장되어있다.

index가 arr.length 와 같은 경우, 더 이상의 원소를 확인할 수 없기 때문에 종료시킨다.

 

그림으로 확인해보면,

위와 같을 때, (r==0) 일 때, visited == true인 값에 대해 출력하면 된다.

 

visited 배열을 사용하지 않고 정수 변수 index로 판별하기

위에서 index라고 표현한 값은 depth로 표현하겠다. (재귀가 호출되면서 층으로 들어가는 것과 같음)

 

index 변수는 0부터 배열의 길이만큼 증가되면서 해당 원소를 조합으로 뽑을지 안 뽑을지 결정하기 위한 변수로 사용된다. 뽑으면 index + 1 (다음 원소 자리), r - 1 로 진행되고, 안 뽑으면 index , r 로 진행된다.

뽑히는 변수가 저장되는 배열의 index 주관.

 

target 변수는 0부터 n 까지 나열된 원소 배열에서 어떤 숫자를 배열에 넣을지 고를 때 쓴다.

전체 원소 배열에서 누구를 뽑는지 안뽑는지 확인하는 인덱스 (현재 대상),

재귀 호출 시마다 +1