티스토리 뷰



 :  n개 중에서 r개를 선택하는 방법의 수.




가령 집합 { A, B, C, D } 에서 2명을 순서와 상관없이 선택하는 방법은 어떤 경우가 있을까요?


{A, B}

{A, C}

{A, D}

{B, C}

{B, D}

{C, D}


위와 같이 총 6가지가 있습니다.




지금부터 이런 부분집합을 구하는 방법에 대해서 알아보겠습니다.

아래와 같은 점화식을 이용해 재귀함수로 구현해 볼 것입니다.



일단 점화식에 대해서 알아보자면 n 개중 r 개를 뽑는 방법은


i)  어떤 특정한 원소를 포함하고 뽑았을 때 

ii) 어떤 특정한 원소를 포함하지 않고 뽑았을 때


두가지로 나뉘어 집니다.





i) 어떤 특정한 원소를 포함하고 뽑았을 때는

이제 그특정한 놈 1개는 이미 뽑혔고 제외한 나머지 n-1 개에서 r-1개만 뽑으면 되니깐 경우의 수는 이고


ii) 어떤 특정한 원소를 포함하지 않고 뽑았을 때는

그 특정한 놈이 포함되지 않는 n-1개에서 여전히 r개를 뽑아야하니깐 경우의 수는 가 됩니다.



이러한 원리로 Combination 객체를 만들어보겠습니다.


class Combination{ private String[] arr; //기준 배열 private Stack<String> st; //조합을 저장할 스택 public Combination(String[] arr){ this.arr = arr; //배열을 받아 객체에 저장한다. st = new Stack<String>(); //스택에 메모리를 할당한다. } public void showStack(){ //스택에 있는 값들을 출력한다. for(int i=0;i<st.size();i++){ System.out.print(st.get(i)+" "); } System.out.println(""); } public void doCombination(int n, int r, int index){ // n : 전체 개수 // r : 뽑을 개수 // index 배열이다보니 현재 배열의 어디를 가리키고 있는지 필요하므로. if(r==0){ //0개를 뽑는다는건 더 이상 뽑을 것이 없다는 말과 같으므로 스택을 출력하고 함수를 종료한다. showStack(); return; } else if(n==r){ //nCr 이라는 건 나머지를 전부 뽑겠다는 말과 같으므로 전부 스택에 넣은 후 출력하면 된다. for(int i=0;i<n;i++)st.add(arr[index+i]);//index부터 n개를 차례대로 스택에 넣고 showStack(); //스택을 보여준다. for(int i=0;i<n;i++)st.pop(); //이후 전부 pop을 시켜 다음 과정을 진행한다. } else{ //저 두가지 예외 사항을 빼면 점화식대로 진행하면 된다. //index를 포함하는 경우 st.add(arr[index]); doCombination(n-1,r-1,index+1); //index를 스택에 넣은상태로 index를 1옮겨 그대로 진행. //index를 포함하지 않는 경우 st.pop(); //index를 제거해주고 doCombination(n-1, r, index+1); //index를 제외한 상태에서 n-1Cr 진행. } } }


주의할 부분은 위에서 재귀함수가 종료되는, 즉 "선택을 완료한" 시점에서 스택을 출력 해야 하는데 r=0 인 경우와 n=r 인 경우가 있습니다. 자세한 설명은 주석으로 써놓았습니다.





아래는 메인 함수 부분입니다.

public static void main(String[] args) {
		// TODO Auto-generated method stub
	{
		String[] a = {"A","B","C","D"};						
		Combination c = new Combination(a);
		c.doCombination(4, 2, 0);
	}

	}


두둥!!! 

잘 나온 것을 확인할 수 있습니다 ^^



댓글
댓글쓰기 폼