C++ 코딩테스트 강좌, 이항계수 구하기 2

안녕하세요! 이번 강좌에서는 이항계수(Binomial Coefficient)의 개념을 심화하여 다룰 것입니다. 이항계수는 조합론의 중요한 개념으로, 주어진 n 개의 원소 중에서 k 개를 선택하는 방법의 수를 나타냅니다. 이 강좌에서 다룰 문제는 “nCr” 또는 “이항계수” 문제로, 효율적인 구현 방법에 대해 알아보겠습니다.

문제 설명

문제는 다음과 같습니다:

주어진 정수 n과 k에 대해 이항계수 C(n, k)를 출력하시오. (단, 0 ≤ k ≤ n ≤ 1000)

이항계수 정의

이항계수 C(n, k)는 다음과 같이 정의됩니다:

C(n, k) = n! / (k! * (n - k)!)

여기서 n!은 n factorial로, n × (n-1) × … × 1의 곱을 의미합니다. 이 정의에 따르면, 이항계수를 계산하기 위해서는 팩토리얼을 계산해야 합니다. 그러나 n이 1000일 경우, n!은 매우 큰 수가 되기 때문에 직접 계산하기보다는 효율적인 방법이 필요합니다.

동적 프로그래밍을 이용한 이항계수 계산

이항계수를 계산하는 보다 효율적인 방법 중 하나는 동적 프로그래밍을 사용하는 것입니다. 이 과정을 통해 이항계수를 효율적으로 계산하는 방법을 살펴보겠습니다.

점화식

C(n, k)는 다음의 점화식으로도 표현됩니다:

C(n, k) = C(n-1, k-1) + C(n-1, k) (단, k > 0)
C(n, 0) = 1 (k가 0일 경우)
C(n, n) = 1 (k가 n일 경우)

이 점화식을 바탕으로 재귀적으로 이항계수를 계산할 수 있지만, 이렇게 하면 중복 계산이 발생하므로 비효율적입니다. 따라서 메모이제이션 또는 동적 프로그래밍 기법을 사용하여 계산할 것입니다.

코드 구현

다음은 C++ 언어로 이항계수를 계산하는 동적 프로그래밍 코드입니다:

#include <iostream>
#include <vector>

using namespace std;

long long binomialCoefficient(int n, int k) {
    vector<vector<long long>> C(n + 1, vector<long long>(k + 1, 0));
  
    // C(n, 0) = 1
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
    }
  
    // C(n, k) = C(n - 1, k - 1) + C(n - 1, k)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, k); j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
  
    return C[n][k];
}

int main() {
    int n, k;
    cout << "Enter n and k: ";
    cin << n >> k;
    cout << "C(" << n << ", " << k << ") = " << binomialCoefficient(n, k) << endl;
    return 0;
}

코드 설명

1. vector<vector<long long>> C(n + 1, vector<long long>(k + 1, 0));: 이항계수를 저장할 2차원 벡터를 선언하고 초기화합니다.

2. C[i][0] = 1;: n이 0일 때, 이항계수는 항상 1이라는 점을 활용하여 첫 번째 열을 초기화합니다.

3. 규칙에 따라 각 값을 계산하며 2차원 벡터 C에 채웁니다.

4. 마지막으로 C[n][k]를 반환하여 결과를 출력합니다.

예제 실행

이제 위의 코드를 실행해 보겠습니다:

Enter n and k: 5 2
C(5, 2) = 10

위의 예제에서 n = 5, k = 2일 때, C(5, 2)의 값은 10으로 올바르게 계산되었습니다.

시간 복잡도 분석

위의 코드에서 이항계수를 동적 프로그래밍을 통해 구하기 때문에 시간복잡도는 O(n * k)입니다. 최악의 경우에 n = 1000일 때, 이 복잡도는 할 수 있는 범위 내입니다. 공간 복잡도는 O(n * k)로, C 벡터를 저장하는 데 필요한 공간을 나타냅니다.

결론

이번 강좌에서는 이항계수를 동적 프로그래밍을 통해 효율적으로 계산했습니다. 이항계수는 조합론, 확률론 등 다양한 분야에서 중요한 개념이므로 이해하고 연습하는 것이 중요합니다. 주어진 문제를 동적으로 푸는 능력을 키우기 위해 다양한 테스트 케이스로 연습해 보세요.

이 강좌가 도움이 되셨길 바라며, 다음 강좌에서 또 만나요!