문제 풀 때마다 까먹어서 이항계수를 정리해보려 한다. 이항계수 nCr 은 n개중 r개를 선택하는 경우의 수를 의미하며 n!/r!(n-r!)로 나타낼 수 있다 알고리즘에서 이항계수를 구할 때 팩토리얼로 일일히 이항계수를 구하면 int범위를 벗어나 오버플로우가 발생하는 경우가 많다. 따라서 BigInteger를 이용해줄 수 있지만 보통은 재귀를 이용한다. 재귀를 이용할 때에도 시간초과가 날 수 있기 때문에 dp로 풀어주는 것이 일반적이다. 이항계수에는 중요한 규칙 두 가지가 있다. 1.nCr = n-1Cr + n-1Cr-1 2.nC0 = nCn = 1 이를 증명해보자 {a1,a2,a3....an}의 부분집합 중 원소의 개수가 r인 것의 개수는 nCr이다 여기서 원소의 개수가 r인 경우는 두가지로 나뉠 수 있..