이항계수

목차

1.개념: 이항계수란 무엇인가

2.적용: Java로 이항계수 계산하기

3.후기: 실제 코딩테스트 대비

 

1.개념: 이항계수란 무엇인가

이항계수는 n개 중 r개를 순서 없이 고르는 방법의 수를 의미합니다.

공식은 다음과 같습니다:

이항계수 공식

• 이항계수는 고등학교 확률과 통계 과목에서 배우는 기본 개념입니다.
• 코딩테스트에서는 조합 문제를 풀거나, 확률 계산 문제를 풀 때 필수적으로 등장합니다.
• 이항계수는 작은 수에서는 손으로 구할 수 있지만, n이 커지면 효율적인 계산법이 필요합니다.

---

2.적용: Java로 이항계수 계산하기

이항계수를 Java로 계산하는 방법은 문제 조건에 따라 선택해야 합니다.

2.1. 기본 방식: 팩토리얼로 직접 계산

간단한 경우에는 팩토리얼을 사용해서 직접 계산할 수 있습니다.

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

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

 

주의:

• n이 크면 long 타입도 넘칠 수 있습니다.
• 시간이 오래 걸릴 수 있어 코딩 테스트에서는 거의 사용되지 않습니다

2.2. DP 방식: 파스칼 삼각형 이용

n과 r이 비교적 작을 때는 **동적 계획법(DP)**을 사용해 빠르게 계산할 수 있습니다.

파스칼 삼각형을 이용한 점화식:

파스칼의 삼각형 점화식

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

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= Math.min(i, r); 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][r];
}

 

특징:

• 메모리를 많이 사용하지만 빠릅니다.
• n이 1000 이하일 때 실용적입니다.

2.3. 모듈러 방식: 10^9+7 나머지로 계산

n이 수십만~백만까지 커지는 경우, 그리고 나머지 연산이 필요한 경우 모듈러 연산을 사용해야 합니다.

static final int MOD = 1_000_000_007;
static final int MAX = 1_000_000;
static long[] fact = new long[MAX + 1];
static long[] inv = new long[MAX + 1];

static void precompute() {
    fact[0] = 1;
    for (int i = 1; i <= MAX; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }

    inv[MAX] = pow(fact[MAX], MOD-2);
    for (int i = MAX-1; i >= 0; i--) {
        inv[i] = (inv[i+1] * (i+1)) % MOD;
    }
}

static long pow(long base, long exp) {
    long result = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

static long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return (((fact[n] * inv[r]) % MOD) * inv[n-r]) % MOD;
}

 

특징:

• n이 1,000,000이어도 빠르게 계산 가능
• 대부분 코딩 테스트에서 요구하는 방식입니다.

3.후기: 실제 코딩테스트 대비

• 현실 코딩 테스트에서는 n과 r이 매우 크거나, 모듈러 연산 결과를 요구하는 경우가 많습니다.
• 따라서 단순 팩토리얼 방식은 거의 못 쓰고, DP 또는 모듈러 방식을 준비해야 합니다.
• 이항계수는 조합/확률 문제 외에도, 그래프 문제, 동적 계획법 문제, 경우의 수 계산 문제에 자주 등장합니다.