728x90 binomial coefficient2 Pascal's triangle (파스칼의 삼각형) // Pascal's triangle What is Pascal's triangle? 좌측의 수식과 같은 이항계수의 값을 구할 때 사용할 수 있다. 하지만 아래 설명을 보면 알 수 있듯 점화식을 활용한 Dynamic Programming의 알고리즘을 사용하는 형태로, n의 값이 상당히 커진다면 사용하기 곤란한 알고리즘이다. n의 값이 상당히 커졌을 경우에는 Lucas Theorem (뤼카의 정리) 를 사용하면 된다. Explanation 위 파스칼의 삼각형을 나타낸 피라미드 모양의 그림에 연두색 값들은, 위에 있는 두 블록의 값의 합과 같다. 또한 양 변들은 nC0, nCn 이 되므로 값이 1이 된다. 이는 이항계수의 성질로서 증명이 된다. Dynamic Programming으로 C[n][k] 와 같은 .. 2021. 1. 28. Lucas's theorem (뤼카의 정리) // Lucas's theorem What is Lucas's theorem? 를 구하는 과정에서 n의 값이 상당히 클 경우 사용하면 유용한 정리이다. n의 값이 적당하다면, n!, ( n-k )!, k! 의 값을 각각 구하여 연산하면 되지만, n의 값이 10억만 되더라도 unsigned long lnog에 조차 담을 수 없게 된다. 이때 뤼카의 정리를 이용할 수 있다. Theorem 먼저, n과 k를 p진법의 전개식으로 나타내보자. 이때, 다음의 합동식이 성립한다. Example 따라서 아래와 같이 나타낼 수 있다. 따라서 답은 0이 된다. Proof // 아직 작성중인 글 입니다.. 2021. 1. 27. 이전 1 다음 728x90
