Combination

안녕하세요 〰️ 오늘은 조합combonation에 대해 알아볼 예정입니다 ❗️ 

백준 6603 번 문제를 푸는 데 사용해보니 어렵더라구요 🤣

그래서 정리도 하고 제대로 알아볼 겸 포스팅해보기로 했습니다 〰️ 

 

 

============  INDEX  ============

 

조합❓ 

조합 구현

조합 구현 - JAVA CODE

 

================================

 

---

첫 번째, 조합❓ 

조합, 간단하게 무엇인지 파악해볼까요 〰️ 

 

 N개의 숫자 중, R개의 숫자를 순서없이 뽑는 것

 

물론 응용을 통해 숫자가 아닌 스트링이나 다른 객체가 될 수도 있겠죠?

예시를 보면서 알아볼게요.

다음의 그림과 같이 N(=4)개의 숫자가 있고, 무작위로 2개를 뽑는다고 생각해보겠습니다.

 

 

4개 숫자들 중에서 2개의 숫자를 순서 상관없이 뽑는다고 하면 아래와 같은 조합을 가집니다.

 

 

 

[0,1][0,2][0,3][1,2][1,3][2,3]  들을 구하는 코드를 같이 구현해볼 예정입니다 〰️

 

 

두 번째, 조합 구현  🔧

 

그럼 이제부터 조합을 어떻게 구현할 지 같이 한 번 볼까요❓ 

재귀를 사용해서 구현해보려고 합니다.

 

먼저, 재귀를 통한 전체적인 진행방식을 살펴볼까요❓ 

 

 

위와 같이 분기처리를 해서 출력을 합니다.

그럼, 어떻게 분기처리를 할지 더 자세히 보도록 하겠습니다.

 

그럼 방문 순서는 어떻게 될까요❓ 

 

 

 

먼저, 다른 분기로 이동하는 조건은 간단합니다.

for문을 돌면서 다른 분기로 이동을 할 예정인데요,

일단 그 분기를 전부 확인하고 다음 분기로 넘어갑니다.

 

1,2,3 -> 1,2,4 -> 1,2,5 -> 1,3,4 -> 1,3,5 -> ...

 

위와 같은 순서입니다.

 

여기에 해당하는 Pseudo code는 아래와 같습니다.

 

class Combination {
    static void combinationUtil(parameters) {
        // ...
        for (int i = start; i < n; i++) {
            data[index] <- isVisited? yes
            combinationUtil(parameters);
            data[index] <- isVisited? no
        }
    }
}

 

먼저, 방문한 곳들을 체크해준 후, 아래 분기로 내려갑니다.

내려가다 해당 분기를 전부 돌았다면 다음 분기 (i++)로 넘어갑니다.

 

그렇다면, 다음으로 한 분기를 어떤 식으로 돌까요 🤔

그건 뽑을 숫자를 이용해서 확인합니다. nCr이라고 하면 r의 개수만큼 채우고 출력을 하죠

 

 

 

 

위와 같이 재귀 함수의 parameter로 r 값을 같이 전달하여, r이 0의 값을 갖는다면 출력을 하고 다음 분기로 넘어갑니다.

여기에 해당하는 Pseudo code는 아래와 같습니다.

 

class Combination {
    static void combinationUtil(parameters) {
        if (r == 0) {
            printCombination();
            return;
        }
    }
}

 

이제, 구현에 대한 설명은 충분한 것 같으니, 직접 코드로 만나보겠습니다 〰️ 

 

 

세 번째, 조합 구현 - JAVA CODE 🖍

코드는 아래와 같습니다.

 

import java.io.*;
import java.util.Arrays;

class Combination {
    static void combinationUtil(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            for (int i = 0; i < n; i++) {
                if (visited[i])
                    System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = start; i < n; i++) {
            visited[i] = true;
            combinationUtil(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

    static void printCombination(int[] arr, int n, int r) {
        boolean[] visited = new boolean[n];

        combinationUtil(arr, visited, 0, n, r);
    }

    public static void main (String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int r = 3;
        int n = arr.length;
        printCombination(arr, n, r);
    }
}

 

 

combinationUtil Method의 parameters를 설명드리자면, 아래와 같습니다.

 

arr - int[] : 데이터들이 담겨있는 배열 (조합을 꺼내올 전체 데이터)

visited - boolean[] : arr[]와 index로 공유하여 data[]의 해당 데이터를 공유했는지 확인

start - int : 다음 분기의 시작점을 명시

n - int : 데이터의 크기를 명시 (nCr 에서 n)

r - int : 크기가 r인 조합을 가져옴 (nCr에서 r)

 

 

설명을 보고 코드를 보니까 조금 더 이해가 가지 않으신가요 ~.~

공부를 하실 때 참고하면서 도움이 되셨으면 좋겠어요❗️