Binomial Coefficients - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:19:35Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:19 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Dynamic Programming]]		상위 문서: [[Dynamic Programming]]

Pinkgo: /* Pascal’s Triangle */

2025-11-18T04:31:18Z

Pascal’s Triangle

← 이전 판		2025년 11월 18일 (화) 04:31 판
16번째 줄:		16번째 줄:
	파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:		파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:
	<math>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>		<math>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>
	바로 위 식의 파스칼의 점화식이다. 이를 직관적으로 표현하면, n번째 원소를 포함하는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>와 n번째 원소를 포함하지 않는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, ~~k-1개만~~ 더 선택하면 된다.</ref>를 합치면 n개의 원소 중에서 k개를 선택하는 경우의 수가 된다는 것이다. 이 방식의 장점은 팩토리얼 계산이 필요 없으며, 단순 덧셈 연산으로 해결 가능하므로 동적 프로그래밍 적용에 매우 적합하다는 것이다.		바로 위 식의 파스칼의 점화식이다. 이를 직관적으로 표현하면, n번째 원소를 포함하는 경우의 수 <math>\dbinom{n-1}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>와 n번째 원소를 포함하지 않는 경우의 수 <math>\dbinom{n-1}{k}</math><ref>이미 n을 포함하므로, k개만 더 선택하면 된다.</ref>를 합치면 n개의 원소 중에서 k개를 선택하는 경우의 수가 된다는 것이다. 이 방식의 장점은 팩토리얼 계산이 필요 없으며, 단순 덧셈 연산으로 해결 가능하므로 동적 프로그래밍 적용에 매우 적합하다는 것이다.

	이를 활용하여, 이항 관계에 대한 기저 조건(base case)을 분석하면 아래와 같다:		이를 활용하여, 이항 관계에 대한 기저 조건(base case)을 분석하면 아래와 같다:

Pinkgo: /* Pascal’s Triangle */

2025-11-18T04:28:30Z

Pascal’s Triangle

← 이전 판		2025년 11월 18일 (화) 04:28 판
13번째 줄:		13번째 줄:

	==Pascal’s Triangle==		==Pascal’s Triangle==
			[[파일:Figure 1. Pascal’s Triangle.png\|섬네일\|Figure 1. Pascal’s Triangle]]
	파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:		파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:
	<math>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>		<math>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>
23번째 줄:		24번째 줄:
	즉, 이항 계수에 대한 점화식은 아래와 같이 구해진다:		즉, 이항 계수에 대한 점화식은 아래와 같이 구해진다:
	<math>\dbinom{n}{k}=		<math>\dbinom{n}{k}=
	\begin{cases}		\begin{cases}
	1, & if\,\,\, k=0 or k=n \\		1, & if\,\,\, k=0 or k=n \\
	\dbinom{n-1}{k-1}+\dbinom{n-1}{k}, & otherwise		\dbinom{n-1}{k-1}+\dbinom{n-1}{k}, & otherwise
	\end{cases}		\end{cases}
	</math>		</math>

	==Binomial Coefficients Implementation==		==Binomial Coefficients Implementation==

Pinkgo: /* Pascal’s Triangle */

2025-11-18T04:26:36Z

Pascal’s Triangle

← 이전 판		2025년 11월 18일 (화) 04:26 판
24번째 줄:		24번째 줄:
	<math>\dbinom{n}{k}=		<math>\dbinom{n}{k}=
	\begin{cases}		\begin{cases}
	1, & if k=0 or k=n \\		1, & if\,\,\, k=0 or k=n \\
	\dbinom{n-1}{k-1}+\dbinom{n-1}{k}, & otherwise		\dbinom{n-1}{k-1}+\dbinom{n-1}{k}, & otherwise
	\end{cases}		\end{cases}

Pinkgo: /* Pascal’s Triangle */

2025-11-18T04:17:18Z

Pascal’s Triangle

← 이전 판		2025년 11월 18일 (화) 04:17 판
14번째 줄:		14번째 줄:
	==Pascal’s Triangle==		==Pascal’s Triangle==
	파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:		파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:
	<math>>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>		<math>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>
	바로 위 식의 파스칼의 점화식이다. 이를 직관적으로 표현하면, n번째 원소를 포함하는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>와 n번째 원소를 포함하지 않는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>를 합치면 n개의 원소 중에서 k개를 선택하는 경우의 수가 된다는 것이다. 이 방식의 장점은 팩토리얼 계산이 필요 없으며, 단순 덧셈 연산으로 해결 가능하므로 동적 프로그래밍 적용에 매우 적합하다는 것이다.		바로 위 식의 파스칼의 점화식이다. 이를 직관적으로 표현하면, n번째 원소를 포함하는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>와 n번째 원소를 포함하지 않는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>를 합치면 n개의 원소 중에서 k개를 선택하는 경우의 수가 된다는 것이다. 이 방식의 장점은 팩토리얼 계산이 필요 없으며, 단순 덧셈 연산으로 해결 가능하므로 동적 프로그래밍 적용에 매우 적합하다는 것이다.

Pinkgo: /* Binomial Coefficients Implementation */

2025-11-15T03:31:56Z

Binomial Coefficients Implementation

← 이전 판		2025년 11월 15일 (토) 03:31 판
52번째 줄:		52번째 줄:
	}		}
	</syntaxhighlight>		</syntaxhighlight>


	==각주==		==각주==

2025년 11월 15일 (토) 03:31에 Pinkgo님의 편집

2025-11-15T03:31:47Z

← 이전 판		2025년 11월 15일 (토) 03:31 판
12번째 줄:		12번째 줄:
	즉, 팩토리얼을 이용하여 직접 계산할 수 있다. 하지만 이는 중간 계산에서 오버플로(overflow)가 발생한 우려가 있다. 예를 들어, <math>20! = 2,432,902,008,176,640,000</math>이므로 중간 계산이 너무 커져서 자료형이 감당하지 못한다. 따라서 직접 팩토리얼 계산보다는 점화식을 이용하는 방법이 더 안전하고 효율적이다.		즉, 팩토리얼을 이용하여 직접 계산할 수 있다. 하지만 이는 중간 계산에서 오버플로(overflow)가 발생한 우려가 있다. 예를 들어, <math>20! = 2,432,902,008,176,640,000</math>이므로 중간 계산이 너무 커져서 자료형이 감당하지 못한다. 따라서 직접 팩토리얼 계산보다는 점화식을 이용하는 방법이 더 안전하고 효율적이다.

	===Pascal’s Triangle===		==Pascal’s Triangle==
	파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:		파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:
	<math>>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>		<math>>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>
29번째 줄:		29번째 줄:
	</math>		</math>

	===Binomial Coefficients Implementation===		==Binomial Coefficients Implementation==
	아래는 위의 점화식을 C코드로 표현한 것이다:		아래는 위의 점화식을 C코드로 표현한 것이다:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">

Pinkgo: 새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: Dynamic Programming ==개요== 이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다. 이항 계수는 수학적으로 아래와 같이 정의된다: $\dbinom{n}{k}=$ "n개 중에서 k개를 선택하는 방법의 수" 이항 계수는 흔히 조합(combination)이라고 불리며, 다양한 분야에 활용된다. 예를 들어 n...

2025-11-15T03:29:34Z

새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: Dynamic Programming ==개요== 이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다. 이항 계수는 수학적으로 아래와 같이 정의된다: <math>\dbinom{n}{k}=</math> "n개 중에서 k개를 선택하는 방법의 수" 이항 계수는 흔히 조합(combination)이라고 불리며, 다양한 분야에 활용된다. 예를 들어 n...

새 문서

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[Dynamic Programming]]

==개요==
이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다. 이항 계수는 수학적으로 아래와 같이 정의된다:
<math>\dbinom{n}{k}=</math> "n개 중에서 k개를 선택하는 방법의 수"
이항 계수는 흔히 조합(combination)이라고 불리며, 다양한 분야에 활용된다. 예를 들어 n명의 사람 중 k명을 뽑는 경우의 수이나, n<math>\times</math>m 격자의 왼쪽 위에서 오른쪽 아래까지, 오른쪽 또는 아래로만 이동할 수 있을 때 가능한 경로의 수<ref><math>\dbinom{n+m}{n}</math>이다.</ref>를 구할 때 사용된다. 이 외에도 경로 문제, 선택 문제, 확률 계산 등 매우 다양한 문제에 등장한다.

이항 계수는 동적 프로그래밍의 전형적인 예시 중 하나이다. 왜냐하면 이항 계수는 반복되는 하위 문제 구조를 갖고 있기 때문이다. 이항 계수는 아래와 같이 계산된다:
<math>\dbinom{n}{k}=\frac{n!}{(n-k)!k!}</math>
즉, 팩토리얼을 이용하여 직접 계산할 수 있다. 하지만 이는 중간 계산에서 오버플로(overflow)가 발생한 우려가 있다. 예를 들어, <math>20! = 2,432,902,008,176,640,000</math>이므로 중간 계산이 너무 커져서 자료형이 감당하지 못한다. 따라서 직접 팩토리얼 계산보다는 점화식을 이용하는 방법이 더 안전하고 효율적이다.

===Pascal’s Triangle===
파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:
<math>>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>
바로 위 식의 파스칼의 점화식이다. 이를 직관적으로 표현하면, n번째 원소를 포함하는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>와 n번째 원소를 포함하지 않는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>를 합치면 n개의 원소 중에서 k개를 선택하는 경우의 수가 된다는 것이다. 이 방식의 장점은 팩토리얼 계산이 필요 없으며, 단순 덧셈 연산으로 해결 가능하므로 동적 프로그래밍 적용에 매우 적합하다는 것이다.

이를 활용하여, 이항 관계에 대한 기저 조건(base case)을 분석하면 아래와 같다:
# <math>\dbinom{n}{0}=1</math>: 아무 것도 고르지 않는 경우는 항상 1가지 (공집합)
# <math>\dbinom{n}{n}=1</math>: 모든 원소를 고르는 경우도 항상 1가지 (전체 집합)

즉, 이항 계수에 대한 점화식은 아래와 같이 구해진다:
<math>\dbinom{n}{k}=
\begin{cases}
1, & if k=0 or k=n \\
\dbinom{n-1}{k-1}+\dbinom{n-1}{k}, & otherwise
\end{cases}
</math>

===Binomial Coefficients Implementation===
아래는 위의 점화식을 C코드로 표현한 것이다:
<syntaxhighlight lang="c">
long binomial_coefficient(int n, int k) {
int i, j;
long bc[MAXN+1][MAXN+1];

// base cases
for (i = 0; i <= n; i++)
bc[i][0] = 1;
for (j = 0; j <= n; j++)
bc[j][j] = 1;

// fill DP table using Pascal’s recurrence
for (i = 2; i <= n; i++) {
for (j = 1; j < i; j++) {
bc[i][j] = bc[i-1][j-1] + bc[i-1][j];
}
}

return bc[n][k];
}
</syntaxhighlight>

==각주==