[알고리즘] DP - 이항계수 (Binomial coefficient)
목차 1. 이항계수의 정의 2. 이항계수 점화식 3. 파스칼의 삼각형 4. 이항계수 구현 정의 이항계수는 이항식을 이항정리로 전개했을 때 각 항의 계수를 나타냅니다. 이항식 $(x + y)^2$ 를 전개한 결과는 다음과 과 같습니다. $(x + y)^2 = x^2 + 2xy + y^2$ 이 때 위의 전개 식에서 각 항의 계수인 [1, 2, 1] 이 나타내는 것이 바로 이항계수 입니다. 이항계수는 조합을 통해 구할 수 있습니다. 이번 포스팅에서는 조합을 통해 이항계수를 구하는 점화식과 이 점화식을 통해서 재귀적으로 그리고 동적계획법으로 이항계수를 구하는 방법에 대하여 알아보도록 하겠습니다. 점화식 이항계수를 구하는 점화식에 대해 알아보도록 하겠습니다. $(x + y)^n$ 이라는 이항식이 주어졌을 때 이항..
2020.04.23