조합(Combination)

조합(Combination)

이번 시간에는 DFS 로 조합을 구현하는 방법을 배워보자.

N 명 중 R 명을 뽑는 경우의 수

nCr 은 n 개의 원소를 갖는 집합에서 r 개의 부분 집합을 고르는 경우의 수를 의미하므로 부분 집합과도 관련이 있다.

구현

// 조합(Combination) : nCr = n-1Cr-1 + n-1Cr
// n 명 중에서 r 명을 뽑는 경우
// 5C3 = 4C2 + 4C3
public class Main {

    static int[][] store = new int[35][35];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(combinationByDfsWithMemoization(sc.nextInt(), sc.nextInt()));
    }

    // 메모이제이션
    static int combinationByDfsWithMemoization(int n, int r) {
        if(store[n][r] > 0) {
            return store[n][r];
        }
        if(n == r || r ==0) {
            return 1;
        } else {
            return store[n][r] = combinationByDfsWithMemoization(n - 1, r - 1) + combinationByDfsWithMemoization(n - 1, r);
        }
    }
}

조합

DFS 를 이용하여 부분 집합 을 구현하는 방법을 모른다면 해당 링크를 통해서 먼저 배우는 것이 좋다.

구현

/**
 * 조합을 이용하여 부분집합 구하기
 * @param arr 원소를 담고 있는 배열
 * @param visited 해당 원소를 사용하는지 여부
 * @param currentIndex 현재 인덱스
 * @param r 뽑을 개수
 */
 static void combinationByDfs(int[] arr, boolean[] visited, int currentIndex, int r) {
     if(r == 0) {
         // r == 0 일때, visited 가 true 인 부분집합을 이용하여 원하는 로직 구현
         logic(arr, visited);
         return;
     }
     if(currentIndex == arr.length) {
         return;
     } else {
         visited[currentIndex] = true; // currentIndex 에 해당하는 원소를 사용한다라는 의미
         combinationByDfs(arr, visited, currentIndex + 1, r - 1); // currentIndex 에 해당하는 원소를 사용하면 R 값을 -1

         visited[currentIndex] = false; // currentIndex 에 해당하는 원소를 사용하지 않는다라는 의미
         combinationByDfs(arr, visited, currentIndex + 1, r); // currentIndex 에 해당하는 원소를 사용하지 안으면 R 값 유지
    }
}