[알고리즘] 조합(Combination)

Generated by DALL-E

 

친구 5명 중에서 2명을 골라 카페에 같이 갈 사람을 뽑는다고 생각해 볼게요.

• “철수, 영희”를 고르는 것과
• “영희, 철수”를 고르는 건

 

순서가 다르지만 결과는 똑같죠?

 

이렇게 순서에 상관없이 선택하는 걸 조합(Combination)이라고 합니다.

(+ 순서에 따라 구분하여 선택하는 건 순열)

 

수학적인 공식은 다음과 같습니다:

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

 

예를 들어 5명 중 2명을 뽑는 경우의 수는:

5C2 = 5! / (2! * 3!) = 10

 

그런데 팩토리얼로 다 해결될까요?

작은 수에서는 괜찮지만 숫자가 커지면 문제는 달라집니다.

예를 들어 100C50을 구하려면 100! 같은 엄청나게 큰 수를 계산해야 하고 이건 long 자료형도 쉽게 넘어서요.

그래서 우리는 좀 더 프로그래밍 친화적인 방법을 찾아야 해요. 바로 재귀와 동적 계획법(DP)이죠!

 

방법 1: 재귀로 조합 구하기(경우의 수)

먼저 재귀(recursion) 방식부터 살펴볼게요.

수학적 공식

수학에서는 다음과 같은 성질이 있어요:

nCr = (n-1)C(r-1) + (n-1)Cr

 

이게 무슨 뜻이냐면…

• 어떤 원소를 뽑는 경우와
• 그 원소를 안 뽑는 경우를 나눠서 생각할 수 있다는 거예요.

 

이 원리를 재귀함수로 옮기면 이렇게 됩니다:

public class CombinationRecursive {

    public static int combination(int n, int r) {
        if (r == 0 || n == r) return 1; // 다 고르거나 하나도 안 고를 땐 경우의 수는 1
        return combination(n - 1, r - 1) + combination(n - 1, r);
    }

    public static void main(String[] args) {
        int n = 5, r = 3;
        System.out.println(n + "C" + r + " = " + combination(n, r));
    }
}

 

어떻게 동작하나요?

• 5C3을 구할 때
  → 4C2 + 4C3을 구하고
  → 4C2는 다시 3C1 + 3C2...
  → 이렇게 점점 더 작은 문제로 쪼개가며 해결하는 거예요.

 

딱 마치 재귀적으로 나무를 타고 내려가는 느낌이에요. 그리고 맨 아래에 도달하면(기저 조건) 값을 반환하죠.

 

하지만... 중복 호출이 너무 많아요

예를 들어 `combination(30, 15)`을 재귀로 풀면 같은 값이 수없이 반복 호출돼요.

그래서 우리는 메모이제이션이라는 메모리를 활용한 방법을 씁니다.

 

방법 2: 동적 계획법(DP)으로 조합 구하기(경우의 수)

DP는 재귀랑 원리는 같지만 이미 계산한 값은 배열에 저장해서 다시 계산하지 않게 해 줘요.

public class CombinationDP {

    static int[][] dp;

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

        if (dp[n][r] != 0) return dp[n][r]; // 저장된 값이 있으면 그대로 사용!

        return dp[n][r] = combination(n - 1, r - 1) + combination(n - 1, r);
    }

    public static void main(String[] args) {
        int n = 30, r = 15;
        dp = new int[n + 1][r + 1];
        System.out.println(n + "C" + r + " = " + combination(n, r));
    }
}

결과

30C15 = 155117520

 

재귀보다 훨씬 빠르고 안정적으로 결과를 확인할 수 있었습니다!

 

팁: 팩토리얼 방식 (작은 수만!)

간단하게 팩토리얼로도 구할 수는 있어요. 다만 숫자가 커지면 오버플로우가 발생할 수 있다는 점만 주의하세요!

public class CombinationFactorial {

    public static long factorial(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) result *= i;
        return result;
    }

    public static long combination(int n, int r) {
        return factorial(n) / (factorial(r) * factorial(n - r));
    }

    public static void main(String[] args) {
        System.out.println("10C4 = " + combination(10, 4));
    }
}

 

실제 조합 리스트까지 구하고 싶다면?

값만 구하는 게 아니라 선택된 조합을 리스트로 보고 싶을 때도 있어요. 이럴 땐 백트래킹처럼 구현하면 됩니다:

import java.util.*;

public class CombinationList {

    public static void combination(int[] arr, boolean[] visited, int start, int r) {
        if (r == 0) {
            print(arr, visited);
            return;
        }

        for (int i = start; i < arr.length; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, r - 1);
            visited[i] = false;
        }
    }

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

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

        combination(arr, visited, 0, r);
    }
}

 

총정리를 해보면...

방식	특징	구현 추천 상황
재귀	코드 간결, 이해 쉬움	작은 n (n ≤ 20 정도)
DP	빠르고 안정적	큰 n (n ≥ 30 이상)
팩토리얼	단순 구현	n이 작고 속도보다 코드 간결함이 중요할 때
조합 리스트	조합 결과 직접 출력	백트래킹 문제, 브루트포스