on
20210817 (화) - 이항정리, DP
20210817 (화) - 이항정리, DP
1. 학습 날짜 : 20210817(화)
2. 학습 시간 : 6시간
3. 학습 주제 : Dynamic Programming, Topological sorting, 다익스트라, 벨만-포드 알고리즘 정리
4. 동료 학습 방법 : 개인
5. 학습 목표 :
동적 계획법에 대한 이해
동적 계획법에 대한 이해 이항 계수 이해
이항 계수 이해 이항 계수와 동적 계획법
이항 계수와 동적 계획법 동적 계획법 관련 문제
동적 계획법 관련 문제 Topological sorting 구현
Topological sorting 구현 다익스트라 구현
다익스트라 구현 벨만-포드 구현
6. 학습 내용 :
이항계수와 DP
이항계수와 이항정리
이항정리
이항식(두 단항식의 합 == 항이 두개인 식)의 거듭제곱을, 이항 계수를 계수로 하는 일련의 단항식들의 합으로 전개하는 정리.
(https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EC%A0%95%EB%A6%AC)
이항식의 거듭제곱 :
$$
(
a
+
b
)
^n
$$
아래 두 식 까지 계산하는것은 귀찮지 않을 수도 있으나,
$$
(a + b)^2, (a + b)^3
$$
아래 두 식을 단항식들의 합으로 표현하고자 한다면 매우 귀찮아지겠다.
$$
(a + b)^9, (a + b)^6
$$
이 때, 이항정리를 사용하면 빠르게 각 항의 계수들을 구할 수 있다.
$$
\displaystyle (a+b)^{n}=\sum_{r=0}^{n} \binom{n}{r} a^{r}b^{n-r}
$$
이항계수
$$
(a + b)^n
$$
꼴의 식을 전개했을 때,
$$
a^{r}b^{n-r}
$$
의 계수를 이항계수라고 한다.
즉, 이항정리에서 알 수 있듯, 이항계수는 아래와 같다.
$$
\displaystyle \binom{n}{r} = \frac{r!} {(n−r)! n!}
$$
이항계수의 재귀적 정의
파스칼의 삼각형을 이용하면 다음과 같은 식을 도출할 수 있다.
$$
\displaystyle \binom{r}{n} =\binom{n-1}{r−1} +\binom{n-1}{r}, (r > 1, r != n)
$$
파스칼의 삼각형을 이해하는 방법은 도식을 보고 경우의 수를 생각하면 된다.
트리의 2nd depth의 가운데 노드인 2 가 2인 이유와 3rd depth의 3 이 3인 이유를 찾으면 이해 가능하다.
2nd depth의 2 로 이르는 경우의 수는 1st의 1과 1 두가지 경우가 존재한다.
3rd depth의 3 으로 이르는 경우의 수는 2nd의 1과 2 두가지 경우가 존재한다.
root 부터 특정 node 에 이르는 Path의 개수를 찾는다고 생각하면 편할듯 하다.
이항계수를 구하는 알고리즘
1. 이항계수 식 nCr 을 이용한 이항계수 구하기 알고리즘
2. 이항계수의 재귀적 정의를 이용한 알고리즘
3. DP를 이용한 알고리즘
Top-down
#include int memo[1001][1001]; void init_memo(int memo[][1001]) { for (int i = 0; i < 1001; i++) for (int j = 0; j < 1001; j++) memo[i][j] = -1; } int binomial_topdown(int n, int k, int memo[][1001]) { if (memo[n][k] != -1) return (memo[n][k]); if (n == k || k == 1) memo[n][k] = 1; else memo[n][k] = binomial_topdown(n - 1, k - 1, memo) + binomial_topdown(n - 1, k, memo); return (memo[n][k]); } using namespace std; int main() { int N, K; int bin; bin = 1; cin >> N >> K; init_memo(memo); bin = binomial_topdown(N + 1, K, memo); cout << bin; for (int i = 0 ; i < 11; i++) { for (int j = 0; j < 11; j++) cout << memo[i][j] << ' '; cout << std::endl; } cout << std::endl; }
bottum-up
4. 3의 최적화
학습에 도움된 사이트 :
from http://pjeongja.tistory.com/98 by ccl(A) rewrite - 2021-08-18 00:25:45