뉴비의 PS 낙서장

C++ 로 조합을 구현하는 방법을 알려주겠다. nCr = n-1Cr-1 + n-1Cr 라는 식을 이용하여 O(nr) 만에 구하는 방법도 있지만, n,r 이 10만정도 된다면 메모리도 시간도 펑펑 터질 것이다. 그래서 이번 글에는 조합을 빨리 구하는 방법을 알려주겠다. (와아앙아앙아아 짝짝짝짝) 순서는 STL내장함수인 next_permutation 을 사용해서 출력하면된다. (이 글은 나중에 추가될 예정이다) 조합을 구할려면 일단 식을 보자 조합 식 이제 이 식을 직접 구하면 되는데 n! 을 구하고 r! 을 구하려고 하면 mod 값에 나눠버리는 경우가 있어서 매우 까다롭다. 예를 들어보자. mod = 7, 구하려고 하는 수는 5C3 이다. 그러면 5! 을 구하고 3! 을 구하고 2! 을 구하고 5! 구한것..