[알고리즘] 점화식(조합)
n개중에서 r개를 뽑는 경우는 nCr이라는 공식을 이용하여 풀수 있다. nCr = n! / r! x (n-r)! 이다 하지만 이것을 컴퓨터에게 그대로 적용시켜 계산하게 되면 오버 플로우가 일어날 수 있다. n!의 경우 n값이 조금만 크더라도 n!값이 엄청 커진다. 이를 방지 하기 위해서 점화식을 이용해서 풀면 된다. nCr = (n - r + 1) / r * nCr-1 nC0 = 1( r = 0일때) 이런식으로 점화식을 이용해서 풀면 오버 플로우를 막을 수 있다. double combination( int n, int r ) { int i; double sum; sum = 1; for( int i =1; i
2008.02.27