[Java] 조합

1. 개요

싸피 교육기간 중 알고리즘을 배우는 시간 있었다.

순열과 조합에 대해 굉장히 중요하다고 하셨고 이를 구현해봤지만 아무리 생각해도 이해가 안갔다.

그래서 구글링을 하며 내걸로 만들고자 이번 포스팅을 준비했다.

2. 목차

1. 조합이란?

2. 조합을 뽑는 방법

3. 구현

 

먼저 조합이 무엇인지와 구조를 이해하고 구현을 했다.

구글에 존재하는 코드를 이해하지 않고 적었다면 이 포스팅으로 이해해보자.

3. 본문

1. 조합이란?

항상 수학시간에 궁금했던 문제다. 순열과 조합은 도대체 무슨차이일까?

필자는 단순 중복여부를 생각했다. 순열은 순서에 상관없이 다 뽑아내고 조합은 중복이 되면 안되는 것이고.

간략하게 생각해보면 위에 말이 맞다. 예시를 들어보자

 

우리는 1,2,3을 사용해서 2개를 뽑을 것이다. 먼저 순서에 상관없이, 즉, 중복이 가능한 형태로 뽑아보자.

{1,2}, {1,3}, {2,1}, {2,3}, {3,1}, {3,2}가 나온다. 여기서 보면 {1,2}, {2,1}은 같은 숫자들만 있지만 순서가 다르므로 뽑았다.

 

반면에 순서가 상관이 있다고 생각해보자. 즉, 위에 뽑은 집합 중에 같은 숫자가 있으면 안되는 것이다.

{1,2}, {1,3}, {2,3}이 된다. {2,1}은 {1,2}와 같은 것으로 포함하지 않았다.

그렇다면 조합은 어떻게 뽑아야하는 것일까?

2. 조합을 뽑는 방법

만약 사과 3개가 있는데 2개를 뽑는다고 생각하자(3C2). 여기서 핵심은 2가지가 된다.

1. 뽑고자하는 것을 포함하고 나머지를 뽑는 경우

2. 뽑고자하는 것을 제외하고 나머지를 뽑는 경우

각 사과에는 1, 2, 3 번호가 적혀있다고 하자. 그 중, 우리는 1번 사과의 경우를 보자.

첫번째 핵심 처럼 1번 사과를 무조건 뽑는다고 하자. 그러면 선택지는 2, 3번 중 1개가 된다.(2C1)

또한 두번째 핵심처럼 1번은 무조건 안뽑는다고 하자. 그러면 선택지는 2, 3을 뽑는 1가지 경우가 된다(2C2)

 

우리가 아는 것처럼 2C2는 (2*1)/(2*1)로 1이 된다. 즉 2, 3을 뽑는 1가지 경우만 존재하는 것이다.

하지만 2, 3번 중 1개를 뽑는 것은 아직 경우의 수가 더 존재한다. 그러므로 한번더 해보는 것이다.

 

이번에는 2번의 경우를 보자.  2번을 뽑거나 안뽑는 경우로 나눌 수 있다.

첫번째 핵심처럼 2번을 뽑는다고 하자. 그렇다면 3번은 못뽑고 버리는 경우가 된다.(1C0)

또한 두번째 핵심처럼 2번을 제외한다고 하자. 그러면 3번만 뽑는 경우가 된다.(1C1)

더이상 뽑을 수 있는 경우의 수가 없으므로 마무리가 된다.

 

여기서 반복되는 구조를 보자. 먼저 3C2 -> 2C1 + 2C2로 표현이 가능하다. 2C2는 1가지 경우만 있으므로 1로 표시한다.

다음 2C1 -> 1C1 + 1C0이 된다. 1 + 1로 표현이 가능하다.

재귀의 형태가 조금은 보이지 않는가? n==r이거나 r == 0인경우는 1을 출력하면 조합의 경우의 수를 구할 수 있다.

또한, nCr = (n-1 C r-1) + (n-1 C r) 로 표현이 가능하다. 말 그대로 뽑은 경우 + 안 뽑은 경우를 더한 것이다.

 

마무리로 전체적인 구조를 보자.

3C2 -> 2C1 + 2C2, 2C2는 1이지만 2C1은 아직 더 구할 수 있다.(재귀)

2C1 -> 1C1 + 1C0은 둘다 1이므로 끝이다.

이제 자바로 구현을 해보자.

    static int getCombCount(int n, int r){
        if(n == r || r == 0){
            return 1;
        }
        else{
            return getCombCount(n -1, r-1) + getCombCount(n-1, r);
        }
    }

nCr = (n-1 C r-1) + (n-1 C r)이 구조를 재귀로 표현했다.

n == r이거나 r == 0이면 1가지 경우밖에 없으니 1을 return 해준다.

3. 구현

이제 전체적인 구현을 해보자. 위의 구조를 이해했다면 쉽게 따라올 수 있을 것이다.

먼저 뽑고자하는 집합과 개수가 존재해야한다. 그래야 n과 r을 구해서 조합을 할 수 있다.

 

다음은 내가 이 숫자를 기준으로 삼았는지 안삼았는지 기준이 필요하다.

그것을 집합과 똑같은 개수를 가진 boolean 배열로 구분한다.

 

마지막으로 뽑았던(기준을 삼았던) 숫자는 더이상 안봐도 되므로 그 숫자를 저장할 변수도 필요하다.

 

필요한 것을 다시 정리해보자.

1. 뽑고자하는 집합 -> 배열(arr)

2. 전체 집합의 개수 -> 배열의 크기(n)

3. 이 숫자를 기준으로 삼았는지 구분 -> 배열(visited)

4. 몇개를 뽑을 것인지 -> 숫자(r)

5. 이 숫자를 사용했다면 다음에는 생각하지 않도록 함 -> 숫자(start)

 

구현준비는 끝났다. 이제 직접 해보자.

 

    static void comb(int[] arr, boolean[] visited, int n, int r, int start){
        if(r == 0){
            //print
            for(int i = 0; i<n; i++){
                if(visited[i]){
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
        }
        else{
            for(int i = start; i<n; i++){
                //i 를 뽑은 상태
                visited[i] = true;
                //현재 뽑은 상태
                comb(arr,visited,n,r - 1, i+1);
                //i + 1을 통해 다음 조건을 설정해줬다.
                visited[i] = false;
            }
        }
    }

백트래킹으로 구해봤다. 단순 재귀는 다음 포스트에 알아보자.(시험준비 해야한다..)

먼저 안쪽 for문을 보자. start를 시작으로 반복하며 visited로 방문 여부를 체크했다.

 

그 후, 재귀 형식으로 r - 1을 통해 start를 뽑은 경우를 보자. 뽑았으므로 visited[i] = true가 된다.

i+1(안뽑고 그냥 넘어가는 경우는 그 다음 코드인 visit[i] = false로 기준을 변경해주었다.

 

마지막으로 r == 0이면 더이상 뽑는 경우가 없기 떄문에 출력을 해준다.

내가 뽑은 숫자라면 출력을 하고 아니면 넘어간다.

 

※재귀의 구조를 알아야 이해가 된다. 재귀를 모른다면 구글링 후 다시보자.

3. 마무리

시험을 위해 코드를 이해하지못하고 그냥 외워버렸다. 그러다보니 조합이 뭔지도 모르고 쓰는 경우가 많았다.

단순히 암기하지말고 이해하면서 코드를 적어보니 바로 이해가 갔다. 하지만 재귀를 아에 모른다면 헷갈릴 수 도 있다.

필자도 재귀의 구조를 이해한지 별로 안됐는데 아직도 어렵다.

 

다음은 순열도 한번 알아볼려고 한다. 일단 시험부터 붙고 보자