반응형
1. 순열
표현 : nPr
서로 다른 n개 중의 r개를 뽑을때, 순서를 포함한 경우의 수
만약, 중복 가능한 n개 중 r개를 뽑으면, 중복 순열
2. 조합
표현 : nCr
서로 다른 n개 중의 r개를 뽑을때, 순서의 상관없이 뽑는 경우의 수
만약, 중복 가능한 n개 중 r개를 뽑으면, 중복 조합
3. 순열 vs 조합
{A, B} 중의 2개를 뽑는 순열 : {A, B}, {B, A}
{A, B} 중의 2개를 뽑는 조합 : {A, B}
4. 조합 점화식
조합은 다음과 같은 점화식이 있습니다. 이 점화식이 나온 이유를 살펴 보겠습니다. n개 중 r개를 뽑는 방법을 2가지로 나누어 생각해 보겠습니다.
1. 어떤 특정한 원소를 포함하고 뽑았을 때
2. 어떤 특정한 원소를 포함하지 않고 뽑았을 때
1. 어떤 특정한 원소를 포함하고 뽑았을 때
특정한 원소 1개를 이미 뽑았다고 가정하면, n-1개가 남아 있습니다. 그리고 이미 1개를 뽑았으므로, r-1개 뽑을 수 있습니다.
2. 어떤 특정한 원소를 포함하지 않고 뽑았을 때
특정한 원소 1개를 포함 하지 않고 n-1개에서 r개를 뽑아야 합니다.
따라서, 위 2가지 경우를 합해야 nCr 이 됩니다.
5. 재귀 함수를 이용한 조합 구현
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
int n = arr.length;
boolean[] visited = new boolean[n];
// 1. 재귀를 이용한 조합 구하기
for (int i = 1; i <= n; i++) {
System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
combination2(arr, visited, 0, n, i);
}
}
// 재귀 사용
// 사용 예시 : combination2(arr, visited, 0, n, r)
public static void combination2(int[] arr, boolean[] visited, int depth, int n, int r) {
if (r == 0) {
print(arr, visited, n);
return;
}
if (depth == n) {
return;
}
// 특정 원소를 포함하고 뽑는 경우
visited[depth] = true;
combination2(arr, visited, depth + 1, n, r - 1);
// 특정 원소를 포함하지 않고 뽑는 경우
visited[depth] = false;
combination2(arr, visited, depth + 1, n, r);
}
// 배열 출력
private static void print(int[] arr, boolean[] visited, int n) {
for (int i = 0; i < n; i++) {
if (visited[i]) {
System.out.print(arr[i] + " ");
}
}
System.out.println();
}
출력 결과
combination2(arr, visited, depth + 1, n, r - 1)를 통해서 '특정 원소를 포함하고 뽑는 경우' 와
combination2(arr, visited, depth + 1, n, r)를 통해서 '특정 원소를 포함하지 않고 뽑는 경우' 재귀 함수로 표현 하였습니다. 여기서, depth + 1이 공식에서 n - 1의 역할을 대신 하였다고 생각 하시면 되겠습니다. boolean visited[] 을 통해서 뽑은 원소를 true 로 할당해 줍니다. 재귀함수를 타고 들어가면서, 뽑아야 될 갯수를 다 뽑았다면 (r == 0) 이라면 visited[]를 통해 출력할 원소들을 확인하고 출력 시켜 줍니다.
6. 백트랙킹을 이용하여 조합 구하기
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
int n = arr.length;
boolean[] visited = new boolean[n];
// 백트랙킹을 이용한 조합 구하기
for (int i = 1; i <= n; i++) {
System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
combination(arr, visited, 0, n, i);
}
}
// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
public static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
// r개의 갯수를 다 뽑음
if (r == 0) {
print(arr, visited, n);
return;
}
for (int i = start; i < n; i++) {
// i를 뽑음
visited[i] = true;
// (i, X)를 뽑기 위해서 재귀
combination(arr, visited, i + 1, n, r - 1);
// 이제 i를 뽑을 일이 없으므로, i 선택 해제
visited[i] = false;
}
}
// 배열 출력
private static void print(int[] arr, boolean[] visited, int n) {
for (int i = 0; i < n; i++) {
if (visited[i]) {
System.out.print(arr[i] + " ");
}
}
System.out.println();
}
출력 결과
이 소스에서는 이전 '재귀 함수를 이용한 구현' 과는 다르게, 아래와 같이 배열의 원소들을 반복문을 돌며, combination(arr, visited, i + 1, n, r - 1)를 통해서 '특정 원소를 포함하고 뽑는 경우' 를 구현 합니다. '특정 원소를 포함하지 않고 뽑는 경우' 를 구현 하지 않는 경우는 for(반복문) 을 통해서 다른 원소에 대해서도 구해 주기 때문입니다.
for (int i = start; i < n; i++) {
// i를 뽑음
visited[i] = true;
// (i, X)를 뽑기 위해서 재귀, 특정 원소를 포함하고 뽑는 경우
combination(arr, visited, i + 1, n, r - 1);
// 이제 i를 뽑을 일이 없으므로, i 선택 해제
visited[i] = false;
}
7. 조합의 갯수 구하기
조합의 갯수 공식은 다음과 같습니다. 이 공식을 코드로 구현하면 아래와 같습니다.
static final int ERROR = -1;
static final int ONE_SIZE = 1;
// 조합의 총 갯수 반환
public static int getCombinationSize(int n, int r) {
if(n == r || r == 0)
return ONE_SIZE;
int denominator = factorial(r) * factorial(n - r);
if (denominator <= 0)
return ERROR;
return factorial(n) / denominator;
}
private static int factorial(int n) {
if (n <= 1)
return n;
else
return factorial(n - 1) * n;
}factorial 함수를 재귀 함수를 이용해서 구현 하고, 위 공식대로 구현 하면 됩니다. 하지만, 위에서 우리가 공부한 점화식을 이용해서 조금 더 간단하게 구현 할 수 있습니다.
8. 조합의 갯수 구하기2
static final int ONE_SIZE = 1;
public static int getCombinationSize2(int n, int r) {
if(n == r || r == 0)
return ONE_SIZE;
else
return getCombinationSize2(n - 1, r - 1) + getCombinationSize2(n - 1, r);
}
이 점화식을 이용하여 구할수 있는데, 재귀 함수의 종료 조건은 (n == r || r == 0) 으로 정의 할 수 있습니다. 조합은 순서가 없습니다. 따라서 n == r 일 경우는 1가지 경우의 수 밖이 없습니다. 그리고 r == 0 일 경우는 뽑고자 하는 모든 개수를 다 뽑았기 때문 입니다.
9. 조합을 반환 하는 함수
위에 함수들은 모두, 뽑는 조합을 출력 하는 함수 였습니다. 반환값을 가지는 시그니처로 변경해서, 필요한 경우 사용 할수 있도록 구현 하겠습니다.
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
int n = arr.length;
boolean[] visited = new boolean[n];
// 1. List<List<Integer>> 로 조합의 경우의 수 모두 반환
// n개중 2개 뽑을 조합
List<List<Integer>> combList = getListAfterCombination(arr, visited, 0, n, 2);
for (List<Integer> list : combList) {
for (Integer value : list) {
System.out.printf("%d ", value);
}
System.out.println();
}
}
// 조합 : n 개 중에서 r 개 선택 조합 반환
public static List<List<Integer>> getListAfterCombination(int[] arr, boolean[] visited, int start, int n, int r) {
List<List<Integer>> combList = new ArrayList<>();
if (r == 0) {
addList(arr, visited, n, combList);
}
for (int i = start; i < n; i++) {
visited[i] = true;
combList.addAll(getListAfterCombination(arr, visited, i + 1, n, r - 1));
visited[i] = false;
}
return combList;
}
private static void addList(int[] arr, boolean[] visited, int n, List<List<Integer>> combList) {
List<Integer> tmp = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (visited[i]) {
tmp.add(arr[i]);
}
}
combList.add(tmp);
}
출력 결과
n개 중 2개를 뽑은 조합을 출력한 결과 입니다. 위에서 백트랙킹을 이용한 구현 소스를 조금 변형 하였습니다.
10. 전체 소스 코드
import java.util.ArrayList;
import java.util.List;
public class Combination {
/**
* 조합 : n 개 중에서 r 개 선택
* 순열과 다르게 순서에 상관 없다.
* [1, 2], [2, 1] 은 같은 하나의 경우 이다.
*/
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
int n = arr.length;
boolean[] visited = new boolean[n];
// 1. 재귀를 이용한 조합 구하기
for (int i = 1; i <= n; i++) {
System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
combination2(arr, visited, 0, n, i);
}
// 2. 백트랙킹을 이용한 조합 구하기
for (int i = 1; i <= n; i++) {
System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
combination(arr, visited, 0, n, i);
}
// 3. n개중 2개 뽑는 조합의 갯수
// factorial 함수 구현
System.out.println();
System.out.println(getCombinationSize(n, 2));
// 4. n개중 2개 뽑는 조합의 갯수
// nCr = n-1Cr-1 + n-1Cr 이용
System.out.println();
System.out.println(getCombinationSize2(n, 2));
// 1. List<List<Integer>> 로 조합의 경우의 수 모두 반환
// n개중 2개 뽑을 조합
List<List<Integer>> combList = getListAfterCombination(arr, visited, 0, n, 2);
for (List<Integer> list : combList) {
for (Integer value : list) {
System.out.printf("%d ", value);
}
System.out.println();
}
}
// 조합 : n 개 중에서 r 개 선택 조합 반환
public static List<List<Integer>> getListAfterCombination(int[] arr, boolean[] visited, int start, int n, int r) {
List<List<Integer>> combList = new ArrayList<>();
if (r == 0) {
addList(arr, visited, n, combList);
}
for (int i = start; i < n; i++) {
visited[i] = true;
combList.addAll(getListAfterCombination(arr, visited, i + 1, n, r - 1));
visited[i] = false;
}
return combList;
}
private static void addList(int[] arr, boolean[] visited, int n, List<List<Integer>> combList) {
List<Integer> tmp = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (visited[i]) {
tmp.add(arr[i]);
}
}
combList.add(tmp);
}
// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
public static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
// r개의 갯수를 다 뽑음
if (r == 0) {
print(arr, visited, n);
return;
}
for (int i = start; i < n; i++) {
// i를 뽑음
visited[i] = true;
// (i, X)를 뽑기 위해서 재귀, 특정 원소를 포함하고 뽑는 경우
combination(arr, visited, i + 1, n, r - 1);
// 이제 i를 뽑을 일이 없으므로, i 선택 해제
visited[i] = false;
}
}
// 재귀 사용
// 사용 예시 : combination2(arr, visited, 0, n, r)
public static void combination2(int[] arr, boolean[] visited, int depth, int n, int r) {
if (r == 0) {
print(arr, visited, n);
return;
}
if (depth == n) {
return;
}
// 특정 원소를 포함하고 뽑는 경우
visited[depth] = true;
combination2(arr, visited, depth + 1, n, r - 1);
// 특정 원소를 포함하지 않고 뽑는 경우
visited[depth] = false;
combination2(arr, visited, depth + 1, n, r);
}
// 배열 출력
private static void print(int[] arr, boolean[] visited, int n) {
for (int i = 0; i < n; i++) {
if (visited[i]) {
System.out.print(arr[i] + " ");
}
}
System.out.println();
}
static final int ERROR = 1;
static final int ONE_SIZE = 1;
// 조합의 총 갯수 반환
public static int getCombinationSize(int n, int r) {
if(n == r || r == 0)
return ONE_SIZE;
int denominator = factorial(r) * factorial(n - r);
if (denominator <= 0)
return ERROR;
return factorial(n) / denominator;
}
private static int factorial(int n) {
if (n <= 1)
return n;
else
return factorial(n - 1) * n;
}
public static int getCombinationSize2(int n, int r) {
if(n == r || r == 0)
return ONE_SIZE;
else
return getCombinationSize2(n - 1, r - 1) + getCombinationSize2(n - 1, r);
}
}반응형
'Algorithm' 카테고리의 다른 글
| 투 포인터(Two Pointer) 알고리즘 (0) | 2020.10.07 |
|---|---|
| 순열 알고리즘 (0) | 2020.10.02 |
| 고정점 찾기 - 이것이 코딩 테스트다 with java (0) | 2020.09.24 |
| 경쟁적 전염 - 백준 18405 번 (0) | 2020.09.24 |
| 볼링공 고르기 (0) | 2020.09.24 |