문제 풀이에 자주 사용하는 순열,조합

 

 

 

• 순열과 조합을 사용하는 문제가 굉장히 자주 등장한다. 
• 순열과 조합을 구하는 탬플릿 사이 사이에 원하는 연산만 추가하면 된다. 
• 이를 정리해두고 자주 보고, 연습해서 필요할 때 빠르게 구현하려고 적어둔다.

 

1.순열 

 

 

1.1 순열 - 원소 중복 x 

 private static void RecursivePermutation(int depth){
        //BASE CASE
        if(depth == r){
           //.. 여기서 순열이 완성되면 할 일 
           // 대표적으로 +1해서 경우의 수를 count한다던지
           // 아니면, 해당 순열에 해당하는 값을 쭉 나열한다던지..
        }else{

            //RECURSIVE CASE
            for(int i=0; i<n;i++){
                if(!check[i]){
                	check[i] = true;
                   //..BASE CASE에서 뭐 할지에 따라 조금씩 다르게 
                    RecursivePermutation2(depth+1);
                    check[i] = false;
                }
            }
        }

    }

• nPm에 해당하는 순열 구해서 뭔가 해야할 때 사용하자! 

 

 

1.2 순열 - 원소 중복 O 

private static void RecursivePermutationWithItSelf(int depth) throws IOException {

        if(depth == r){
           //..
        }else{

            for(int i=0; i<n;i++){
                //..
                RecursivePermutationWithItSelf(depth+1);
            }

        }

    }

• check만 빼주면 된다! 

 

2. 조합 

 

2.1 조합 - 원소 중복 x 

static void recursiveComb(int start, int depth) {

        //BASE CASE
        if(depth == r){
        	//..
        }else{

        //RECURSIVE CASE
        for(int i=start; i<n;i++){
            
        //..
         recursiveComb(i+1,depth+1);
             
            
        }

       }

}

• nCr 에 해당한다

 

2.2 조합 원소 중복 O

 private static void RecursiveCombinationWithItSelf(int depth,int start) {

        if(depth == r){

           //..

        }else{

            for(int i=start; i<n; i++){
                output[depth] = numbers[i];
                RecursiveCombinationWithItSelf(depth+1,i);
            }

        }

• 다음 start에 i+1대신 i를 넣어주면 중복 원소 포함 조합이 된다. 

 

2.3 조합 점화식 구현 

• 조합을 다음의 점화식으로 표현할 수 있다.
  • n-1Cr-1 + n-1Cr
    • n-1Cr-1 : 특정 원소 포함해서 뽑기 - > 원소 하나 뽑았으니 나머지 r-1에서 뽑겠다.
    • n-1Cr : 특정 원소 포함 안하고 뽑기 -> 원소 아직 안뽑았으니 r에서 뽑겠다.
  • 위 두가지 경우를 합쳐야 n개 중 r개를 뽑는 경우의 수가 나오게 된다. 
  • {4,2,9}를 예시로 들어보자 3C2 
    • 4번 뽑기 (n-1Cr-1)
      • 2번 뽑기 {4,2}
      • 2번 안뽑기 
        • 3번 뽑기 {4,3}
        • 3번 안뽑기 
    • 4번 안뽑기 (n-1Cr)
      
      • //.. 이하 생략 
  • 위와 같은 점화식을 코드로 옮겨보자 

 //nCr
 static int combination(int n, int r){
		//BASE CASE
        if(r == 0){
        
        //더 뽑을 수 있는게 없다 
        // 뭔가 로직 처리 
      	return;
       
       }else{
       
       //특정 원소 포함해서 뽑기 n-1Cr-1에 해당 
       //보통 원소를 출력하거나, 조합을 전부 보고 싶은 경우 여기서 컬렉션에 담음 
       // ex st.add(i);
       	combination(n-1,r-1);
        
        //특정 원소 포함 안하고 뽑기 n-1Cr에 해당
        //여기서 원소 제거
        //st.pop();
        combination(n-1,r);
        
        }
    

 }