이항 계수 2

문제

언어

  • JavaScript

순서도

  1. 다이나믹 프로그래밍 기법을 이용해서 이항 계수 표 (파스칼의 삼각형) 만들기
  2. 이항 계수 표를 이용해서 문제에서 주어진 N 과 K 의 이항 계수 출력

문제 풀이 step 1

  • 이항 계수란 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수입니다.
  • 정의를 보면, 백준 11051번 이항 계수 2 의 이항 계수 정의 사진
    • 이항 계수가 정확히 뭔지는 모르겠지만, 저희에게 익숙한 조합의 가짓수로 생각하면 될 것 같습니다.
    • 즉, N 과 K 의 이항계수는 NCK 입니다. (C 는 조합을 의미합니다.)

문제 풀이 step 2

  • 문제에서 주어진 N 과 K 의 이항 계수를 10,007 로 나눈 나머지를 구하라고 합니다.
  • 위의 정의에 따라서 ( n! / (k! (n - k)!) ) % 10007 의 식으로 구하면 될 것 같은데, 결론은 불가능합니다.
    • 메모이제이션 기법을 이용해서 1000! 까지 배열 (Array) 에 저장합니다. 이 때, 값이 너무 커지니까 10,007 로 나눈 나머지 값을 저장합니다.
    • 이렇게 하면, Array[1000] 은 1000! % 10007 의 값을 저장하게 됩니다.
    • 그리고 식을 이용해서 Array[n] / (Array[k] * Array[n - k]) 을 구하면 될 것 같지만, 나머지 연산의 특성상 식이 성립하지 않습니다.
    • 우리가 배열을 채울 때, 값이 너무 커지니까 나머지 값들을 저장하면서 배열을 채웠었습니다.
    • 즉, 위에서 우리가 구한 식은 사실 Array[n] % 10007 / (Array[k] % 10007 * Array[n - k] % 10007) 입니다.
    • 하지만 나머지 연산의 특성상 ( Array[n] / (Array[k] * Array[n - k]) ) % 10007 식과 Array[n] % 10007 / (Array[k] % 10007 * Array[n - k] % 10007) 식은 동일하지 않습니다.

문제 풀이 step 3

  • 나머지 연산에 대해서 다시 알아보자면, 나머지 연산에서 동일한 식은 다음의 두 가지 입니다.
    • (A + B) % M = ((A % M) + (B % M)) % M
    • (A x B) % M = ((A % M) x (B % M)) % M
    • 즉, 더하기와 곱하기 연산에 대해서 성립합니다.

문제 풀이 step 4

  • 따라서 식을 이용해서 바로 구하는 방법은 불가능하고, 파스칼의 삼각형을 이용하면 쉽게 구할 수 있습니다.
  • 파스칼의 삼각형이란 이항계수를 삼각형 모양의 기하학적 형태로 배열한 것이라고 합니다.
  • 파스칼의 삼각형은 다음과 같습니다. 백준 11051번 이항 계수 2 의 파스칼의 삼각형 사진
    • 서문이 길지만 중요한 것은 NCK = (N-1)C(K-1) + (N-1)CK 입니다. (C 는 조합을 의미합니다.)
    • 즉, 파스칼의 삼각형에서 특정 값은 자신을 기준으로 한 칸 위의 왼쪽 값과 오른쪽 값을 더한 값입니다.
  • 즉, 파스칼의 삼각형을 이용하면 더하기 연산을 통해서 이항 계수의 값을 구할 수 있게 되는 것입니다.
  • 위에서 알아봤듯이 더하기 연산은 나머지 연산을 해도 값이 달라지지 않습니다.
  • 따라서 위에서 알아낸 정보를 이용해서 다이나믹 프로그래밍 기법으로 파스칼 삼각형을 구현합니다.
    • 여기서, 점화식은 dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k] 이고, dp[n][0] = dp[n][n] = 1 입니다.
    • 이 식을 이용해서 dp 배열을 채워줍니다.
  • 그리고 구현한 파스칼 삼각형에서 주어진 N 과 K 의 이항계수를 구해서 출력하면 정답이 됩니다.
  • 추가 설명은 주석에 작성하겠습니다.

Reference.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const MOD = 10007;
	const [n, m] = input[0].split(" ").map(Number);

	const dp = Array.from({length: n + 1}, () => []);

	// base
	dp[0] = [1];

	// bottom-up
	for (let i = 1; i < n + 1; i++) {
		// NC0, NCN 은 0 입니다. (C 는 조합을 의미합니다.)
		dp[i][0] = dp[i][i] = 1;

		for (let j = 1; j < i; j++) {
			// 점화식, 파스칼의 삼각형에서 특정 값은 자신을 기준으로 한 칸 위의 왼쪽 값과 오른쪽 값을 더한 값
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
		}
	}

	return dp[n][m];
};

console.log(solution(input));