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

안녕하세요, 이번 포스트에서는 이항계수를 구하는 문제에 대해 다루어 보겠습니다.
이항계수는 조합론에서 매우 중요한 개념으로, 주어진 n개 중에서 k개를 선택하는
방법의 수를 나타냅니다. 이 문제를 해결하기 위해 다이나믹 프로그래밍을 사용할 것이며,
또한 자바스크립트를 활용하여 이를 구현해 보겠습니다.

문제 정의

주어진 정수 n과 k에 대해 이항계수 C(n, k)를 계산하시오. 이항계수는 다음과 같이 정의됩니다.

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

이 문제를 해결하는 데 있어 고려해야 할 몇 가지 조건이 있습니다:

0 ≤ k ≤ n
n은 자연수로 제한된다.
입출력의 정확성 및 효율성을 고려해야 한다.

이항계수의 성질

이항계수는 다음과 같은 중요한 성질을 가지고 있습니다:

C(n, 0) = 1
C(n, n) = 1
C(n, k) = C(n-1, k-1) + C(n-1, k)

위의 성질을 활용하면 재귀적으로 이항계수를 구할 수 있습니다. 하지만
재귀적인 방법은 시간 복잡도가 높아서 큰 n에 대해 비효율적일 수 있습니다.
따라서 다이나믹 프로그래밍을 통해 반복적인 계산을 줄이는 방법으로 접근하겠습니다.

다이나믹 프로그래밍 접근법

이항계수를 효율적으로 계산하기 위해서 2차원 배열을 사용하여 이전 계산값을 저장해
반복적으로 사용하는 방식으로 구현합니다. 특히, 이항계수는 대칭성을 가지기 때문에
n과 k의 값에 따라 메모이제이션을 사용하여 중복 계산을 방지할 수 있습니다.

알고리즘 설명

n+1 x n+1 크기의 2차원 배열 dp를 생성합니다.
dp[i][j]에 C(i, j)의 값을 저장합니다.
기본 조건을 설정합니다:
- dp[i][0] = 1, for all i (k=0일 때)
- dp[i][i] = 1, for all i (k=n일 때)
이항계수를 재귀적 성질을 통해 계산합니다:
- dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

자바스크립트 구현

        
function binomialCoefficient(n, k) {
    // n+1 x n+1 크기의 dp 배열 초기화
    const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));

    // 초기 조건 설정
    for (let i = 0; i <= n; i++) {
        dp[i][0] = 1; // C(i, 0) = 1
        dp[i][i] = 1; // C(i, i) = 1
    }

    // 다이나믹 프로그래밍을 통한 이항계수 계산
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= Math.min(i, k); j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }

    return dp[n][k]; // 최종 결과 반환
}

// 예제 사용
const n = 5;
const k = 2;
console.log(`C(${n}, ${k}) = `, binomialCoefficient(n, k)); // 출력: C(5, 2) = 10

결론

이번 포스트에서는 이항계수를 계산하는 방법에 대해 다루어 보았습니다.
다이나믹 프로그래밍을 활용하여 효율적으로 이항계수를 구하는 과정을 살펴보았습니다.
이 문제는 이론적인 접근뿐만 아니라 프로그래밍적으로도 매우 유용하며,
다양한 알고리즘 문제를 해결하는 데 활용될 수 있습니다.
앞으로 더 다양한 알고리즘 문제들을 다루어 보며 코딩 실력을 높이는 데 도움이 되기를 바랍니다.