조합 계산 정리

조합 계산 공식 (이항계수)

 

조합의 점화식

 

점화식에 따른 재귀함수 작성

public static int cur(int n, int k) {
    if(n == k || k ==0) return 1;

    return cur(n - 1, k - 1) + cur(n - 1, k);
}

* 공식에 따라 n 과 k가 동일할 때와 k가 1일 때는 값이 1뿐이 안나온다.

 

* 이러한 공식말고 쉽게 생각해보면 

예를 들어 4C3이라 할 때 4개 중 3개를 고르는데 경우의 수가 4 * 3 * 2 이다(순열). 이걸 순서를 없애고자 3! 로 나눠주면 바로 답이 나온다.

 

(4*3*2) / (3*2*1) = 4 

 

여기서 위의 곱하는 횟수와 아래의 곱하는 횟수가 같기 때문에 같은 for 문 내에서 분자와 분모를 계산할 수 있다.  

public int solution(String[] names) {
    int n = 4;
    int k = 3;

    int numerator = 1; // 분자
    int denominator = 1; // 분모 
    for (int i = 0; i < k; i++) {
        numerator *= n - i;
        denominator *= (i + 1);
    }

    return numerator / denominator;
}