알고리즘 조합

● 조합을 이용한 알고리즘을 구현 할 수 있다.

● 공식 n-1Cr + n-1Cr (n개의 숫자, r 조합의 개수)

조합이란? n개의 숫자 중 r개를 순서와 상관 없이 뽑는 경우를 의미한다.

(순열이란 n개의 숫자 중 r개를 순서와 관련하게 뽑는 경우)

예를 들어

[1,2,3] 3개의 숫자가 존재하고 2개를 조합하여, 순서와 상관없이 뽑게 되면

n-1Cr-1 + n-1Cr = 2C1 + 2C2 = 2+1 = 3가지의 경우의수가 된다.

(nCr = n!/ r! )

그렇다면 조합의경우의수를 어떻게 구현해야하는지 Java 소스 구현을 통해 알아보자.

 

1. 조합의 경우의 수 구하기

재귀호출 방법을 이용한 경우의 수를 구해보자.

예를들어 3C2은 

분모 3* 2! = 2 *1! = 3*2*1  , 분자 2 * 1! = 2  

재귀호출 방법으로 1! 나올때까지 호출 해주면 된다.

public static void main(String[] args) {
        // TODO Auto-generated method stub
      
    }
    /*팩토리얼 계산*/
    static int combination(int n){
        int cnt = 0;
        if(n <=1) return 1;
        
        return n*combination(n-1);
        
    }
    /*조합 계산*/
    public static int combination1(int n, int r) {
		if(n == r || r == 0) 
			return 1; 
		else 
			return combination(n - 1, r - 1) + combination(n - 1, r); 
	}