이항계수 알고리즘 java

이항계수를 구하는 알고리즘을 Java로 구현한 것이다. 이항계수는 다음과 같이 2차원 배열로 생성이 가능하다. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 어떤 규칙인지 눈에 보일 것이다. nCk 일 때, 위에서부터 n이 0, 1, 2, 3, ... 이런 식으로 나가는 것이고, 오른쪽으로는 k는 0, 1, 2, 3, ... 이런식으로 나간다. 맨 위의 1은 0C0, 그 밑에는 1C0, 1C1이 그 밑에는 2C0, 2C1, 2C2가 되는 것이다. 숫자를 구할 때 바로 위의 수 + 바로 위에서 왼쪽에 있는 수를 더해서 구하면 된다. 아래는 알고리즘이다. if(n2 > n1 / 2) n2 = n1 - n2; 입력받은 수 n1이 n이고 n2가 k이다. nCk = nC(n-k)를 적용한 것이다. 왜냐하면 k의 수를 줄이면 배열의 크기가 줄어 들어 좀 더 효울적이기 때문이다. public static int bin(int n, int k) { int[][] a...

원문링크 : 이항계수 알고리즘 java