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

이번 강좌에서는 이항 계수(Binomial Coefficient)에 대해 자세히 알아보고, 이를 구하는 효율적인 코드를 자바로 작성해보겠습니다. 이항 계수는 조합의 수를 셀 때 사용되며, “nCr”로 표기합니다. 이 문제를 통해 알고리즘의 중요성을 이해하고, 코딩 테스트에 필요한 스킬을 향상시키는 기회를 갖게 될 것입니다.

이항계수란?

이항계수는 주어진 n과 r에 대해 r개의 원소를 n개의 원소 중에서 선택하는 방법의 수를 말합니다. 수학적으로는 다음과 같이 표현합니다:

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

여기서, n!은 n의 팩토리얼을 의미하며, n! = n × (n-1) × … × 1입니다. 이항 계수를 구하는 공식이 단순해 보일 수 있지만, n이 커지면 팩토리얼 값이 급격히 증가하므로 큰 수 계산에 유의해야 합니다.

문제 정의

다음의 문제를 해결해봅시다:

문제: 0 ≤ n ≤ 30, 0 ≤ r ≤ n 범위의 정수가 주어질 때, 이항계수 C(n, r)를 효율적으로 계산하는 자바 프로그램을 작성하시오.

문제 접근 방식

이 문제를 해결하기 위해서는 기본적인 방법부터 시작해 볼 수 있습니다. 하지만 n의 최대값이 30이므로, 단순하게 팩토리얼을 사용하는 것은 비효율적일 수 있습니다. 그러므로 우리는 동적 프로그래밍(Dynamic Programming) 기법을 활용하여 이 문제를 해결하겠습니다.

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

동적 프로그래밍을 사용하면 중복되는 계산을 피할 수 있습니다. 이항계수를 구하는 데 있어 다음과 같은 성질을 활용합니다:

C(n, r) = C(n-1, r-1) + C(n-1, r)

이 성질을 통해, 기본 경우 C(n, 0) = C(n, n) = 1와 같은 값을 초기화하고, 나머지 값을 채워 나가는 방식으로 이항 계수를 계산할 수 있습니다.

자바 코드 구현

아래는 동적 프로그래밍을 이용하여 이항 계수를 계산하는 자바 코드입니다:

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

        // C(n, 0) = 1
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        // C(n, n) = 1
        for (int i = 0; i <= n; i++) {
            dp[i][i] = 1;
        }

        // Fill the dp table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, r); j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }

        return dp[n][r];
    }

    public static void main(String[] args) {
        int n = 5; // 예시를 위한 값
        int r = 2; // 예시를 위한 값
        System.out.println("C(" + n + ", " + r + ") = " + binomialCoefficient(n, r));
    }
}

코드 설명

위 코드는 이항계수를 계산하기 위한 동적 프로그래밍 접근 방식입니다. 각 단계에 대한 설명은 아래와 같습니다:

2D 배열 생성: 이항 계수를 저장하기 위해 (n+1) x (r+1) 크기의 2D 배열을 생성합니다.
기본 경우 초기화: C(n, 0)과 C(n, n)을 초기값으로 1로 설정합니다.
DP 테이블 채우기: 이중 루프를 통해 각 이항 계수를 계산합니다. C(n, r) = C(n-1, r-1) + C(n-1, r) 공식에 따라 값을 채웁니다.
결과 반환: 최종 결과는 dp[n][r]에 저장됩니다.

테스트 및 결과

코드를 실행하여 다양한 n과 r 값에 대해 이항계수를 확인해봅시다. 예를 들어, n=5, r=2일 때 결과가 어떻게 되는지 살펴봅시다.

C(5, 2) = 10

이는 5개의 원소 중 2개를 선택하는 경우의 수가 10임을 의미합니다. 다양한 경우에 대해 실행해보면 각 조합의 수를 확인할 수 있습니다.

복잡도 분석

이 코드의 시간 복잡도는 O(n * r)입니다. 공간 복잡도 또한 O(n * r)로, DP 테이블을 저장하기 위한 공간을 고려하면 충분히 효율적입니다. n이 30까지 가능하므로 큰 문제에서도 무리 없이 작동할 것입니다.

마무리 및 추가 학습 자료

이번 강좌에서는 이항계수를 계산하는 방법과 이를 위한 자바 코드를 작성하는 과정을 살펴보았습니다. 여기에 제시된 알고리즘은 코딩테스트에서 유용하게 사용할 수 있는 기술입니다. 이항계수에 관한 더 깊이 있는 이해를 위해서는 조합론 및 확률론에 관한 자료를 추가로 학습하는 것도 좋습니다.

앞으로도 다양한 알고리즘 문제를 풀어보며 코딩 테스트 대비와 실력을 쌓아가길 권장합니다.