본문 바로가기
My Image
Algorithm/Algorithm

[Algorithm] JAVA로 중복이 없고, 순서도 없는 조합(Combination) 구하기!

by Lim-Ky 2018. 6. 13.
반응형

JAVA로 중복이 없고, 순서도 없는 조합(Combination) 구하기!



이번 시간은 JAVA로 중복이 없는 조합을 구하는 방법에 대해 알아보겠습니다.


우선 1,2,3 구슬이 있습니다.


3개중에 2개를 뽑는다고 했을때, 모든 경우의 수는 다음과 같습니다.


1,2

1,3

2,1

2,3

3,1

3,2 


총 6가지 입니다. 팩토리얼 개념으로 접근하면 3*2 = 6 가지임을 알 수 있습니다. 


이제 여기서 중복을 제거한 경우의 수만 따진다면,


1,2

1,3

2,3


총 3가지 입니다. 이를 조합이라고 합니다. 수학적인 기호로 나타내면! nCr 입니다. 


즉, 중복이 없고, 순서도 없는 경우의 수(조합)입니다.


n은 총 갯수, r 은 뽑아야 할 갯수 입니다. 


저는 배열과 재귀함수를 통해 nCr에 대해서 구해보겠습니다.


재귀함수의 특징을 이용하여, 모든 경우의 수를 다 탐색하도록 하겠습니다. 백트래킹 개념과 동일합니다. 백트래킹이란 어렵지 않습니다. 


모든~~~ 경우를 다 탐색하는 것이라 생각하시면 됩니다.


자! 1,2,3 이 3개중에 2개를 뽑는 경우는 단계적으로 쪼개보면 다음과 같이 생각할 수 있습니다.


현재 index가 가리키고 있는 녀석을 뽑는경우!!

현재 index가 가리키고 있는 녀석을 뽑지 않는 경우!!


자! 예를 들어 첫번째 구슬인 1을 뽑을 경우와 안뽑는 경우 2가지 경우로 뻗어 나갈 수 있습니다.

그 다음, 1을 뽑았으니 두번째 구슬인 2를 뽑을 경우와 안뽑는 경우로 또 2가지로 경우로 뻗어 나갈 수 있습니다.

또 하나! 1을 안뽑은 경우도 있었죠? 1을 안뽑은 경우 그냥 스킵하고 두번째 구슬인 2를 뽑을 경우와 안뽑는 경우 2가지로 뻗어 나갑니다.


자!! 그럼 이렇게 계속 뻗어 나가면 도대체 언제 끝나나요...? 


당연히 끝날 조건을 생각하셔야겠죠??? 생각해봅시다. 어떤 경우에 끝이 나는지! 재귀함수를 이용하기 때문에 재귀함수를 구현할 땐 항상 종료하거나 재귀를 탈출하는 조건을 설정하는 것이 굉장히 중요합니다!! 말이 길어지네요. 자 언제 끝나는지 생각해볼까요?


첫번째! 처음 우리가 원한 2개의 구슬을 모두 뽑은 경우! 이럴경우 r == 0 으로써 0개를 뽑는다는 의미로 모두 뽑았으니 종료합니다.

두번째! 아무것도 안뽑았건, 한개를 뽑았건, 중요치 않습니다. 모든 구슬을 다 탐색한 경우 종료합니다.


이를 그림으로 도식화했습니다. 






 왼쪽의 가지는 뽑는 경우이고, 오른쪽 가지는 안뽑는 경우입니다.


다검사라는 뜻은 종료된 것입니다. 느낌이 오시나요??? 


간단합니다. .Target을 계속 한단계씩 올리면서 뽑는 경우와 안뽑는 경우 모든 경우의 수를 다 탐색하는 것입니다.


이를 코드로 그래도 옮기면 다음과 같습니다!



package Combination;

import java.util.Arrays;

public class Combination {
    public static void main(String[] ar){
        Combination ex = new Combination();
        int[] arr = { 1, 2, 3 };
        int n = arr.length;
        int r = 2;
        int[] combArr = new int[n];

        ex.doCombination(combArr, n, r, 0, 0, arr);
    }

    public void doCombination(int[] combArr, int n, int r, int index, int target, int[] arr){
    	System.out.println("=> "+n+" "+r+" "+index+" "+target);
        
    	// r ==0 이란 것은 뽑을 원소를 다 뽑았다는 뜻.
    	if(r == 0){
        	System.out.println(Arrays.toString(combArr));
            for(int i=0; i<index; i++)System.out.print(arr[combArr[i]] + " ");
          
            System.out.println();
        
        //끝까지 다 검사한 경우..1개를 뽑은 상태여도 실패한 경우임 무조건 return 으로 종료
        }else if(target == n){ 
        	
        	return;
        
        }else{
            combArr[index] = target;
            // (i) 뽑는 경우 
            // 뽑으니까, r-1
            // 뽑았으니 다음 index + 1 해줘야 함
            doCombination(combArr, n, r-1, index+1, target+1, arr);
            
            //(ii) 안 뽑는경우
            // 안뽑으니까 그대로 r
            // 안뽑았으니, index는 그대로!
            // index를 그대로하면, 예를 들어 현재 1번 구슬을 comArr에 넣엇어도 다음 재귀에 다시 엎어쳐서 결국 1구슬을 뽑지 않게 된다.
            doCombination(combArr, n, r, index, target+1, arr); 
        }
    }
}



재귀는 공부하면 할수록 참 오묘하고 재미있는 녀석입니다.... 어렵기도 하구요...ㅎㅎ

개인적으로 위와 같이 도식화해서 직접 한단계 한단계 그림을 그리면서 재귀의 특성을 이해하면 처음 입문하실 때 도움이 될거라 생각합니다.

이상으로 JAVA로 조합구하는 알고리즘 시간을 마치도록 하겠습니다.



참고사이트 : https://gorakgarak.tistory.com/523?category=265216







반응형

댓글