자바 조합(combination) 정리

개요

조합은 n개 중에서 k를 골라서 뽑는 방법을 구하는 통계용어다.

예를들어 10개 중에서 3개를 고른다고 가정하자.

그러면 10*9*8 / 3 * 2 * 1 => 120가지다.

물론 크기가 너무 크기 때문에 조금더 작은 걸로 교채해보면

5개중애 2개를 고른다면

총 10가지가 나온다.

공을 5개 가지고 있다고 생각해보자.

초기

이들을 2개씩 나눠 보자.

이런식으로 나눌 수 있다는 것을 확인 할 수 있다. 

물론 순서는 상관이 없냐고 물어볼 수 있다. 결론부터 말하면 상관없다.

검파나 파검이나 뽑는 사람 입장에서는 파란색 공과 검정색 공을 뽑기 때문이다. 즉, 아무 상관없다는 뜻이다. 

 

이제 이 방법을 토대로 코드를 작성해보자.

c++이나 파이썬같은 경우, 조합과 관련해서 라이브러리를 재공해준다.

하지만 자바는 전혀 제공하지 않는다.

몇 가지 방법이 있는데 내가 사용하는 방법 1개와 

다른 방법 1개를 소개하려고 한다.

 

재귀 이용

내가 이용하는 방법은 순수하게 재귀를 이용하는 방법이다.

    static void combination(int depth, int index, int value) {
        if (depth == m) {
            List<int[]> temp = new ArrayList<>();
            for(int i = 0; i < m; i++) {
                temp.add(new int[]{chicken.get(now[i])[0], chicken.get(now[i])[1]});
            }
            total.add(temp);
            return;
        }
        if (value == chicken.size()) {
            return;
        }
        now[index] = value;
        combination(depth+1,index+1,value+1);
        combination(depth,index,value+1);
    }

이 코드는 치킨배달문제이다. 간단히 설명하면

깊이, 인덱스, value값을 이용해서 조합을 이용했다. 현재 now라는 배열의 크기는 조합을 구하려는 갯수다.
즉, 3개를 구한다고 가정하면 now의 크기는3이 되고, 2면 now의 크기는 2가 된다는 뜻이다.

즉, m이라는 값이 치킨집을 뽑는 수인데 이 숫자랑 똑같다.

만약에, 전체 리스트를 전부 순회를 했다면?

당연히 탈출해야 한다.

여기까지 알고 나면 depth와 value가 뭔지는 모르지만, 언제 종료되는지 알게 되었다.

이제 본격적으로 설명해보자면,
depth는 치킨집을 1부터 m번까지 뽑는 방법이다.
즉, depth가 증가했다는 뜻은, 다음 치킨집을 뽑겠다는 의미고,
증가 하지 않았다는건 이번 치킨집을 뽑겠다는 뜻이된다.

어찌보면 boolean타입과 비슷해 보인다.

아니 같을지도 모른다. 아무튼

그러면 index는 뭐냐 바로 now배열에 값이 들어 있는인덱스가 된다.

하지만 now로는 치킨집이 정확히 어느 위치에 있는지 알려주지 않는다.

다만 now[0]번째에 몇번이 들어 있다 정도만 알 수 있다.

즉, value로 전체 치킨집을 순회하면서 값을 넣어주고

now을 이용해서 값을 추가해 준다.
여기서 주의 할점은 한쪽은 증가하고 있고,
다른쪽은 증가되지 않고 있다. 이는 now[0]에 값이 들어 왔어도 다른 값이 들어 왔다는것을 의미한다.

이제 이렇게 구한 now값을 가지고 치킨집의 위치를 구해주면 치킨집에 관련된 조합코드가 완성된다.

now[i]값은 i값에 따라 변화하기 때문에
value값에 따라 변화되기 때문에,  매번 값이 달라진다는것을 목표로 두고 있다.

 

백트래킹

사실 위 방법보다 이 방법을 더 먼저 알았으나 현재 위 코드에 더 적응이 되있는 상태이므로

이 코드는 잘 모른다. 그렇기 때문에 다른 블로그에 있는 코드를 참조해 왔다.

// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
    if(r == 0) {
        print(arr, visited, n);
        return;
    } 

    for(int i=start; i<n; i++) {
        visited[i] = true;
        combination(arr, visited, i + 1, n, r - 1);
        visited[i] = false;
    }
}

출처 : https://bcp0109.tistory.com/15

이 코드도 위랑 별 차이가 없는 것 같다.

다만 vlaue가 start가 되버리고,

2번의 재귀가

viseted배열로 처리된다는 점빼고는 같은 것 같다.

 

다시 보니 두번 재귀를 하는 이유는 초기화를 시도하기 위함으로 해석된다. 

전체적으로 보니까 같은 코드인것 같다.

나중에 치킨 배달 문제를 이 방법으로 풀어 봐야 겠다.

 

조합으로 푸는 다른 문제들... 

6603번: 로또

 

15655번: N과 M (6)

 

15650번: N과 M (2)

 

조합으로도 풀수 있는 문제들...

18428번: 감시 피하기

 

14502번: 연구소

 

많은 문제를 풀지 못해서 여기가 한계인 듯 싶다.ㅜㅜ;;;