이항 계수

이항 계수 ?

• 이항 계수는 조합을 계산할 때 사용되는 수학적 개념으로, n개의 원소 중 k개의 원소를 고르는 경우의 수를 의미한다.

$$

C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

💡 이항 계수 계산 방법

• 팩토리얼 사용 :

public class BinomialCoefficient {

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

    public static long binomial(int n, int k) {
        if (k > n) return 0;
        return factorial(n) / (factorial(k) * factorial(n - k));
    }

    public static void main(String[] args) {
        System.out.println(binomial(5, 2)); // Output: 10
        System.out.println(binomial(10, 3)); // Output: 120
    }
}

• DP(파스칼의 삼각형) 사용 : 이항 계수를 재귀적 관계를 통해 $O(n^2)$에 계산한다. → 중복 계산을 방지하여 효율적이나, 값이 크면 메모리 사용량이 증가한다 !

public class BinomialCoefficient {

    public static int binomial(int n, int k) {
        int[][] dp = new int[n + 1][k + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= Math.min(i, k); j++) {
                if (j == 0 || j == i) {
                    dp[i][j] = 1; // 경계 조건
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
        }

        return dp[n][k];
    }

    public static void main(String[] args) {
        System.out.println(binomial(5, 2)); // Output: 10
        System.out.println(binomial(10, 3)); // Output: 120
    }
}

• 모듈러 연산 사용 : 매우 큰 값에서도 효율적으로 계산이 가능하며, $O(n + \log p)$ 복잡도를 가진다 !

public class BinomialCoefficient {

    static final int MOD = 1_000_000_007;
    static long[] factorial;

    public static void precomputeFactorials(int n) { // n! 값을 미리 계산하여 배열에 저장
        factorial = new long[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i % MOD;
        }
    }

    public static long modInverse(long a, long mod) { // 모듈러 연산에서의 나눗셈을 처리하기 위해 곱셈의 역원
        return power(a, mod - 2, mod); // 페르마의 소정리를 이용하여 a^{-1} mod m = a^{m-2} mod m로 처리
    }

    public static long power(long base, long exp, long mod) { // 빠른 거듭제곱 알고리즘으로 a^b mod m을 계산.
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = result * base % mod;
            }
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }

    public static long binomial(int n, int k) { // 이항 계수 공식
        if (k > n) return 0;
        return factorial[n] * modInverse(factorial[k], MOD) % MOD * modInverse(factorial[n - k], MOD) % MOD;
    }

    public static void main(String[] args) {
        int n = 10, k = 3;
        precomputeFactorials(n);
        System.out.println(binomial(n, k)); // Output: 120
    }
}

<aside> 💡

모듈러 연산 ?

• 어떤 수를 특정 수로 나눈 나머지를 계산하는 연산이다 !

  $$

  a(피제수)\mod m(나누는 수) = r \quad \text{(단, } 0 \leq r < m\text{)} $$

• 페르마 소정리의 곱셈의 역원을 이용한 나눗셈 연산 수행 → 모듈러 연산에선 나눗셈이 정의되어 있지 않기 때문에 !

  • 곱셈의 역원: $a^{-1}$ ( m이 소수이고, a와 m이 서로소인 경우 ) → $a^{-1}$(모듈러 m에서의 곱셈의 역원)을 $a^{m-2}\mod m$로 계산할 수 있다는 것

  $$

  (a \cdot a^{-1}) \mod m = 1 \\ . \\.\\ a^{m-1} = 1 \mod m \\ . \\ . \\ a^{m-1} = a \cdot a^{m-2}

  $$

</aside>