자바 조합(Combination) 구하기(nCr)

이직 준비를 위해 알고리즘 문제 풀이 연습을 하다가 매 번 막히는 부분이 있습니다.

바로 조합(Combination)을 만드는 부분인데요, 어느 정도 시도해보다가 잘 안 되면 답을 베끼는 것이 몸에 배다보니 그 순간에만 대충 이해하고 넘어가고, 다음 번에 비슷한 유형의 문제를 만났을 때 어김 없이 문제를 풀지 못하는 저의 모습이 너무 한심해 기록으로 남겨보려고 합니다.

조합(Combination)

먼저 조합은 n 개중 r 개를 고르는 경우의 수를 구할 때 사용합니다. 수식으로는

이렇게 표현합니다.

재귀(Recursive) 알고리즘을 이용해 조합 구하기

앞서 살펴본 수식을 점화식 형태로 표현하기 위해 규칙을 찾아봅시다.

 

5개 중 3개를 선택하는 경우, 하나를 반드시 포함한 상태에서는 나머지 4개 중 2개만 선택하면 되고, 하나를 제외한 상태에서는 나머지 4개 중 3개를 선택해야 합니다.

 

4개 중 2개를 선택해야 하는 경우에도 마찬가지로 하나를 반드시 포함한 상태에서는 3개 중 1개, 하나를 제외한 상태에서는 3개중 2개를 선택해야 합니다.

 

3개 중 1개를 포함해야 하는 경우는 3개 중 1개를 고르는 3가지 밖에 없습니다.

 

이를 점화식으로 표현하면 아래와 같습니다.

 

 

이렇게 표현할 수 있습니다.

 

이를 다시 소스 코드로 작성하면 아래와 같습니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class CombinationGenerator {
    public static void main(String[] args) {
        CombinationGenerator combinationGenerator = new CombinationGenerator();
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter n and r sequentially: ");
        int n = scanner.nextInt(), r = scanner.nextInt();
        List<int[]> combinations = combinationGenerator.generateCombinations(n, r);
        for (int[] combination : combinations) {
            System.out.println(Arrays.toString(combination));
        }
    }

    private List<int[]> generateCombinations(int n, int r) {
        List<int[]> combinations = new ArrayList<>();
        generateCombinationsRecursively(combinations, new int[r], 1, n, 0);
        return combinations;
    }

    private void generateCombinationsRecursively(List<int[]> combinations, int[] elements, int current, int end, int index) {
        if (index == elements.length) {
            combinations.add(elements.clone());
            return;
        }
        if (current > end) {
            return;
        }
        elements[index] = current;
        generateCombinationsRecursively(combinations, elements, current + 1, end, index + 1);
        generateCombinationsRecursively(combinations, elements, current + 1, end, index);
    }
}

generateCombinationsRecursively 메서드는 두 번의 재귀 호출을 합니다.

 

첫 번 째는 현재 엘리먼트를 포함하고, 두 번 째는 현재 엘리먼트를 제외한 뒤 다음 엘리먼트를 포함하게 합니다.

반복(Iteration)을 이용하여 조합 구하기

반복적 접근 방식에서는 초기 조합으로 시작합니다.

 

그런 다음 모든 조합을 생성 할 때까지 현재 조합에서 다음 조합을 계속 생성합니다.

 

현재 조합에서 다음 조합을 얻기 위해 현재 조합에서 증가 할 수 있는 가장 오른쪽 위치를 찾습니다.

 

그런 다음 위치를 증가시키고 해당 위치의 오른쪽에 가능한 가장 낮은 조합을 생성합니다.

 

소스 코드로 표현하면 다음과 같습니다.

public List<int[]> generateCombinationsIteratively(int n, int r) {
    List<int[]> combinations = new ArrayList<>();
    int[] combination = new int[r];
    for (int i = 0; i < r; i++) {
        combination[i] = i + 1;
    }
    while (combination[r - 1] < n) {
        combinations.add(combination.clone());
        int t = r - 1;
        while (t != 0 && combination[t] == n - r + t) {
            t--;
        }
        combination[t]++;
        for (int i = t + 1; i < r; i++) {
            combination[i] = combination[i - 1] + 1;
        }
    }
    return combinations;
}