[GDG - 스터디] 이항 계수 구하기

이항 계수

이항 계수 ?

• 이항 계수는 조합을 계산할 때 사용되는 수학적 개념으로, 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) {
        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);
    }

    public static long power(long base, long exp, long mod) {
        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{)} $$

</aside>

---

문제: 이항 계수 1 (백준 11050)

문제 링크

 

---

알고리즘 [접근 방법]

• 앞서 살펴봤던 세가지 방법 중 한가지 방법을 택해서 이항 계수 계산 코드를 구현하면 된다. → 아마 이 문제에선 어떤 방식을 택해도 통과가 되겠지만, 가장 효율적인 모듈러 연산을 이용한 방식으로 해결한다.

---

해결 코드

import java.io.*;
import java.util.*;

public class Main {

    static final int MOD = 1_000_000_007;
    static int N, K;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        System.out.println(binomialCoefficient());
    }

    public static long binomialCoefficient() {
        if (K > N) return 0;
        if (K == 0 || K == N) return 1;

        long[] factorial = new long[N + 1];
        factorial[0] = 1;

        for (int i = 1; i <= N; i++) {
            factorial[i] = factorial[i - 1] * i % MOD;
        }

        long numerator = factorial[N];
        long denominator = (factorial[K] * factorial[N - K]) % MOD;

        return numerator * modInverse(denominator, MOD) % MOD;
    }

    public static long modInverse(long a, int mod) {
        return power(a, mod - 2, mod);
    }

    public static long power(long base, long exp, int mod) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
}

---

정리

• 모듈러 연산을 이해하고 이를 이용해 이항 계수를 구하는 공식을 그대로 구현할 줄 알면 된다.

 

https://thin-azimuth-2a9.notion.site/GDG-14bf4ee21c0080f9bc5ff67b3cfad2fa?pvs=4

GDG 스터디 - 이항 계수 구하기 | Notion