조합론
[알고리즘 소개]
이항 계수를 삼각형 모양으로 배열한 것
[알고리즘 특징]
- dp 사용
[코딩 방법]
- 2차원 dp배열 dist를 생성
- dist[i][j]는 $\binom{i}{j}$를 의미
- 모든 정수 p에 대해 dist[p][0] = 1로 초기화, 나머지 부분은 0으로 초기화
- $\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}$를 사용하여 점화식 dist[i][j] = dist[i - 1][j] + dist[i - 1][j - 1] 도출
[시간 복잡도]
$O(NK)$
[공부용 링크]
'정리 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 뤼카의 정리 (Lucas' Theorem) (2) | 2021.03.27 |
|---|---|
| [알고리즘] 페르마의 소정리를 이용한 이항 계수 (2) | 2021.03.27 |
| [알고리즘] 분할 정복을 이용한 거듭제곱 (0) | 2021.03.25 |
| [알고리즘] 유클리드 호제법 (Euclidean Algorithm) (0) | 2021.03.25 |
| [알고리즘] 플로이드-와샬 (Floyd-Warshall) (0) | 2021.03.25 |