728x90 pascal's triangle1 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. 이전 1 다음 728x90
