파이썬은 라이브러리에 다 있는 데 자바는 없다. 참 곤란하다. 조합, 순열 같은거 많이 쓰여서 만들어 놨으면 좋겠는데 직접 구현해야 한다. 이번엔 조합을 구현해보자.

접근법

우선 조합은 순서에 상관없이 숫자들을 뽑는 것이다. 알고리즘으로 적으로 다양한 방법으로 구현 할 수 있는 데 나는 조합을 쪼개서 구현할 것 이다.

6개중 4개를 뽑는 조합의 수를 생각해보자. 6개의 수 중 임의의 수를 하나 정하면 5개 3개를 뽑는 조합과 뽑은 수를 안뽑는 다고 가정하면 5개 중 4개를 뽑는 조합의 합으로 나타낼 수 있다.

예를 들어서 arr = {1, 2, 3, 4, 5, 6, 7}의 배열 중 3개들 뽑는 조합의 수를 구해보자.
우선 임의로 3을 선택해서 뽑았다고 가정하자. 그럼 나머지 수 6개중 2개의 조합만 뽑으면 된다. 그리고 3을 선택하는 경우는 계산한거니 3을 제외하고 6개 수중 3개를 뽑으면 전체 조합의 수를 뽑을 수 있다.

그럼 핵심 아이디어는 이 짓거리를 계속 반복한다는 것이다. 위의 예를 들으면 임의로 3을 선택해서 조합을 수를 직접 구하는 게 아니고 여기서 또 쪼개는 것이다. 0개를 뽑는 조합의 수가 1이므로 트리를 역산해서 다 더하면 된다. 나는 이걸 dp로 구현할 것 이다.

import java.util.Arrays;

public class CombinationDP {
    public static void main(String[] args) {
        int n = 5; // 전체 원소의 개수
        int r = 3; // 선택할 원소의 개수

        System.out.println("C(" + n + ", " + r + ") = " + calculateCombination(n, r));
    }

    private static long calculateCombination(int n, int r) {
        long[][] memo = new long[n + 1][r + 1];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dp(n, r, memo);
    }

    private static long dp(int n, int r, long[][] memo) {
        if (r == 0 || n == r) {
            return 1;
        }

        if (memo[n][r] != -1) {
            return memo[n][r];
        }

        long result = dp(n - 1, r - 1, memo) + dp(n - 1, r, memo);
        memo[n][r] = result;
        return result;
    }
}

private static long dp(int n, int r, long[][] memo) {
if (r == 0 || n == r) {
return 1;
} 이 조건식을 사용하여 1을 얻고 2차원 배열을 이용해서 조합의 수를 기록해준다.