728x90
조합(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 값 유지
}
}
728x90
'Algorithms > 기본 지식' 카테고리의 다른 글
LIS(최장 증가 부분 수열) (0) | 2022.01.11 |
---|---|
부분 집합 구하기(DFS) (0) | 2022.01.03 |
깊이 우선 탐색(DFS) (0) | 2022.01.03 |
위상 정렬 (0) | 2021.12.14 |
신장 트리와 크루스칼 알고리즘 (0) | 2021.12.13 |