조합

물건이나 개념들을 순서에 상관없이 선택하여 만들어지는 모든 경우의 수를 조합(Combination)이라고 합니다. 조합은 일상생활에서도 많이 사용되며, 특히 수학, 통계학, 공학 등 다양한 분야에서 중요하게 다루어진다.

조합은 크게 두 가지 유형이 있다:

중복을 허용하지 않는 조합(Combination without repetition):

한 번 선택한 물건이나 개념을 다시 선택하지 않는 경우를 말합니다. 예를 들어, {A, B, C}라는 세 개의 물건이 있을 때, 이들을 2개씩 선택하는 조합은 {A, B}, {A, C}, {B, C}로 총 3가지 경우가 있다.

중복을 허용하는 조합(Combination with repetition)

한 번 선택한 물건이나 개념을 여러 번 선택할 수 있는 경우를 말합니다. 예를 들어, {A, B, C}라는 세 개의 물건이 있을 때, 이들을 2개씩 선택하는 중복 조합은 {A, A}, {A, B}, {A, C}, {B, B}, {B, C}, {C, C}로 총 6가지 경우가 있습니다.

중복을 허용하지 않는 조합을 구하는 방법은 주로 "n 개 중에서 r 개를 선택하는 조합의 수"를 구하는 공식으로 풀 수 있다. 이를 nCr로 표기하며, 공식은 다음과 같다:

nCr = n! / (r! * (n - r)!)

여기서 n은 원소의 총 개수, r은 선택할 원소의 개수를 나타냅니다. 또한 "!"는 팩토리얼을 의미하는 기호로, n!은 n부터 1까지의 모든 양의 정수를 곱한 값입니다.

중복을 허용하는 조합의 경우에는 복잡한 공식이 사용되며, 일반적으로 반복문이나 재귀적인 방법을 이용하여 구할 수 있습니다.

public class Example {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        int r = 2; // 선택할 원소의 개수

        boolean[] visited = new boolean[arr.length];
        function(arr, visited, 0, 0, r);
    }

    public static void function(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;
                function(arr, visited, i + 1, depth + 1, r);
                visited[i] = false;
            }
        }
    }
}

변수설명

arr: 조합을 만들 원소들이 들어있는 배열입니다. 이 배열로부터 조합을 생성합니다.

visited: 원소가 선택되었는지를 나타내는 boolean 배열입니다. arr의 원소를 선택할 때마다 해당 원소의 인덱스에 해당하는 값이 true로 표시됩니다.

start: 재귀 함수 호출 시, 해당 원소 이후의 인덱스부터 시작하여 조합을 생성합니다. 이를 통해 중복된 조합을 방지합니다.

depth: 현재까지 선택한 원소의 개수를 나타냅니다. 조합이 완성되면 depth와 r이 같아지게 됩니다.

r: 선택할 원소의 개수를 지정합니다. 조합의 길이가 됩니다.
함수는 재귀적으로 동작하며, depth와 r이 같아지면 선택된 원소들을 출력합니다. 그렇지 않은 경우, 반복문을 통해 아직 선택되지 않은 다음 원소를 선택하고, 다시 원소를 선택하지 않은 상태로 재귀 함수를 호출하여 모든 조합을 찾습니다.

함수의 동작 순서

depth와 r이 같아지면, 선택된 원소들을 출력하고 함수를 종료합니다.
그렇지 않은 경우, start 인덱스부터 반복문을 돌면서 선택되지 않은 원소를 선택하고, 해당 원소를 선택한 상태로 재귀 함수를 호출합니다.
재귀 함수가 종료되면, 해당 원소를 선택하지 않은 상태로 visited 배열을 되돌립니다.반복문이 끝나면, 함수 호출한 곳으로 돌아가고, 다음 인덱스의 원소를 선택하도록 반복합니다.위의 과정을 반복하여 모든 조합을 찾습니다.