조합
조합이란 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 말한다.
(위키백과 - 수학에서 조합은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다. 그 경우의 수는 이항 계수이다.)
예를 들어 [1, 2, 3] 배열에서의 조합은 아래와 같이 나온다.
[1, 2]
[1, 3]
[2, 3]참고
순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다.
말 그대로, 순서가 존재하는 열이라는 것이다.
즉 순열에서 { 1, 2, 3 }과 { 1, 3, 2 } , { 2, 1, 3 } 등 모두 다른 결과를 가져온다. 순서가 다르기 때문이다.
조합은 순서가 상관이 없는 모임을 의미한다.
순서가 상관없기 때문에 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은 것으로 취급을 한다.
즉 1, 2, 3 이라는 3개의 숫자로 이루어져 있다는 점에서 똑같은 취급을 하는 것이 조합이다.
설명
조합은 기호 nCr로 나타내며
nCr = n-1Cr-1 + n-1Cr로 나타낼 수 있다.
즉 조합은 하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우 이 둘의 합을 나타낸다.
예를 들어 (1, 2, 3) 중에서 2개를 뽑는 조합이라고 생각해보면 -> 3C2
- (1, X) - 1을 뽑는 경우(하나의 원소를 선택할 경우)
- (X, X) - 1을 뽑지 않는 경우(하나의 원소를 선택하지 않는 경우)
이처럼 2가지로 나뉠 수 있다.
- 1을 뽑은 경우 나머지 (2, 3) 중 1개를 선택해야 함. (총 2개의 경우 (1, 2) (1, 3)) -> 2C1
- 1을 뽑지 않은 경우 (2, 3) 모두 선택해야 한다. (총 1개의 경우 (2, 3)) -> 2C2
즉 (1, 2, 3)에서 2개를 뽑는 조합은 둘을 합해 (1, 2) (1, 3), (2, 3) 총 3가지가 된다.
이게 이해가 잘 가지 않는 다면 수학에서의 예를 들어보겠다.
사과 5개가 있고 각 사과에 1, 2, 3, 4, 5 번호가 적혀있다.
그중에서 3개를 뽑을 것이다.
사과3을 무조건 포함하고 나머지 2개를 뽑으면 4C2일 것이다.
그리고 사과 3을 포함하지 않고 뽑으면 4C3이다.
두 경우를 합하면 결국 사과 5개 중에서 3개를 뽑는 것이 된다. 5C3
(전체에서 - 3이 있는 경우 = 3이 없는 경우 이렇게 생각하면 또 이해하기 쉬워진다!)
자 이게 조합의 기본 원리이고 특징이다!
이를 바탕으로 결국 더 이상 쪼개지지 않을 때까지 즉, nC0 = 1이 될 때까지 구한다면 nCr을 구할 수 있게 되는 것이다.
이를 코딩으로 구해보자!
1. 조합 경우의 수 구하기
위의 설명을 바탕으로 nCr을 구해보자.
3개 중에서 2개를 뽑는 경우를 예를 들어보자.
3C2 = 2C1 + 2C2 >... > 3C0 = 1이 될 때까지 재귀 호출을 통해 구현한다.
- 재귀를 통해 호출을 하다 r == 0이 될 경우, 즉 r개를 다 뽑은 경우는 더 이상 선택의 여지가 없으므로 1을 리턴.
- 전체 개수n이 뽑아야 할 개수 r과 같아졌다면 역시 다 뽑는 것 말고 선택의 여지가 없으므로 1을 리턴한다.
- 그 이외에는 원소를 선택할 경우 + 선택하지 않을 경우 둘의 합을 계속 재귀로 호출하면 되는 것이다.
public class Combination {
public static void main(String[] args) {
System.out.println(combination(3, 2)); //3개중에서 2개를 뽑는 조합의 경우의 수
}
public static int combination(int n, int r) {
if(n == r || r == 0)
return 1;
else
return combination(n - 1, r - 1) + combination(n - 1, r);
}
}2. 조합 구하기(진짜 뽑아진 애들)
이제 조합의 경우의 수 말고 진짜 뽑아져 나온 조합들을 구해보자.
조합을 구하는 방법은 배열의 처음부터 마지막까지 돌며
- 현재 인덱스를 선택하는 경우
- 현재 인덱스를 선택하지 않는 경우
이렇게 두가지로 모든 경우를 완전 탐색하는 것이다.
- arr : 조합을 뽑아낼 배열
- r : 조합의 길이(뽑을 개수)
- visited : 조합에 뽑혔는지를 확인하기 위한 배열
순열과 달리 조합은 r을 유지할 필요가 없으므로 숫자를 하나 뽑을때마다 하나씩 줄여준다.
r == 0 일 때가 r 개의 숫자를 뽑은 경우이다.
반복문을 통해 1개부터 배열의 크기까지 돌며 r개를 뽑는다.
백트래킹의 방법, 재귀의 방법 두 가지 방법으로 구현하는 법을 알아보자!
int[] arr = {1, 2, 3}; //조합을 만들 배열
boolean[] visited = new boolean[arr.length]; //조합에 뽑혔는지를 확인하기 위한 배열
//1. 백트래킹을 이용해 구현
for(int r = 1; r <= arr.length; r++) { //반복문을 통해 1개부터 배열의 크기 까지 r개를 뽑는다
comb1(arr, visited, 0, r);
}
//2. 재귀를 이용해 구현
for(int r = 1; r <= arr.length ; r++) {;
comb2(arr, visited, 0, r);
}
2-1. 백트래킹 이용해 구현
start 변수는 기준이다.
start를 기준으로 start 보다 작으면 뽑을 후보에서 제외, start 보다 크면 뽑을 후보가 된다.
예를 들어 [1, 2, 3] 배열이 있고 start 가 0부터 시작한다.
조합을 뽑는 comb 함수에 들어오면 먼저 i 정점부터 시작하는 for 문에 들어간다.
만약 0 인덱스에 있는 값 1을 뽑는다면 visited [i]는 true가 되고, 뽑지 않는다면 visited[i] 는 false가 된다.
즉, 1을 선택한 경우(visited[i] = true)와 선택하지 않은 경우(visited[i] = false) 둘 다 봐야 한다.
하지만 더 이상 1은 고려 대상이 아니기 때문에 다음 for 문은 2부터 즉, i + 1부터 시작해주어야 한다.
static void comb1(int[] arr, boolean[] visited, int start, int n, int r) {
if(r == 0) {
print(arr, visited, n);
return;
} else {
for(int i = start; i < n; i++) {
visited[i] = true;
comb1(arr, visited, i + 1, n, r - 1);
visited[i] = false;
}
}
}2-2. 재귀 이용해 구현
depth 변수는 현재 인덱스. 0부터 시작한다.
현재 인덱스를 뽑는다면 = true, 뽑지 않는다면 visited[depth] = false로 진행한다.
마찬가지로 뽑은 경우와 뽑지 않은 경우 모두 봐야 하고, 그때 이전에 본 값들은 더 이상 고려 대상이 아니기 때문에 depth 은 무조건 1 씩 증가한다.
depth == n 이 되면 모든 인덱스를 다 보았으므로(배열의 끝에 도착 -> 조합 만들 수 X) 재귀를 종료한다.
또한 r == 0이 되면 뽑을 개수를 다 뽑아 조합이 완성되으니 재귀를 종료한다.
//2. 재귀 사용해 구현
static void comb2(int[] arr, boolean[] visited, int depth, int n, int r) {
if(r == 0) {
print(arr, visited, n);
return;
}
if(depth == n) {
return;
} else {
visited[depth] = true;
comb2(arr, visited, depth + 1, n, r - 1);
visited[depth] = false;
comb2(arr, visited, depth + 1, n, r);
}
}2-1, 2-2 전체 코드
public class Combination {
public static void main(String[] args) {
int[] arr = {1, 2, 3}; //조합을 만들 배열
boolean[] visited = new boolean[arr.length];
//1. 백트래킹을 이용해 구현
System.out.println("-------- 1. 백트래킹 ---------");
for(int r = 1; r <= arr.length; r++) {
System.out.println("\n" + arr.length + "개 중에 " + r + "개 뽑음");
comb1(arr, visited, 0, r);
}
//2. 재귀를 이용해 구현
System.out.println("\n---------- 2. 재귀 ----------");
for(int r = 1; r <= arr.length ; r++) {
System.out.println("\n" + arr.length + "개 중에 " + r + "개 뽑음");
comb2(arr, visited, 0, r);
}
}
//1. 백트래킹을 이용해 구현
static void comb1(int[] arr, boolean[] visited, int start, int r) {
if(r == 0) {
print(arr, visited);
return;
} else {
for(int i = start; i < arr.length; i++) {
visited[i] = true;
comb1(arr, visited, i + 1, r - 1);
visited[i] = false;
}
}
}
//2. 재귀를 이용해 구현
static void comb2(int[] arr, boolean[] visited, int depth, int r) {
if(r == 0) {
print(arr, visited);
return;
}
if(depth == arr.length) {
return;
} else {
visited[depth] = true;
comb2(arr, visited, depth + 1, r - 1);
visited[depth] = false;
comb2(arr, visited, depth + 1, r);
}
}
// 배열 출력
static void print(int[] arr, boolean[] visited) {
for(int i = 0; i < arr.length; i++) {
if(visited[i] == true)
System.out.print(arr[i] + " ");
}
System.out.println();
}
}출력
-------- 1. 백트래킹 ---------
3개 중에 1개 뽑음
1
2
3
3개 중에 2개 뽑음
1 2
1 3
2 3
3개 중에 3개 뽑음
1 2 3
---------- 2. 재귀 ----------
3개 중에 1개 뽑음
1
2
3
3개 중에 2개 뽑음
1 2
1 3
2 3
3개 중에 3개 뽑음
1 2 3 2-3. 번외 - visited 배열을 쓰지 않고 정수 변수 index로 판별해 구해보기
이 방법은 0~n까지 숫자의 조합을 구하는 방법이다.
그래서 배열은 사이즈 n만큼 그냥 0부터 n까지 채워진다.
코드는 0, 1, 2 3개의 원소에서 2개의 조합을 구한다.
index변수는 0부터 시작해 배열의 인덱스를 증가시키면서 해당 인덱스를 뽑을지 안 뽑을지를 결정해 조합을 만들기 위한 변수이다.
(뽑는다면 index + 1, r - 1 / 안 뽑는다면 index 그대로, r 그대로)
target 변수는 0~n까지 나열된 원소 배열 안에서 어떤 숫자를 타깃으로 해 배열에 집어넣을지 고를 때 쓰인다.
combination() 함수가 실행될 때마다 항상 +1씩 해 판별한다.
index 변수에 따라 target에 있는 숫자가 뽑힐지 안 뽑힐지가 결정된다.
target+1이 nCr에서 n-1 -> n-2 -> n-3 ->... -> 1까지 가는 역할을 수행한다.
재귀와 그에 대한 종료 조건은 2-2와 같은 방식이다.
public class Combination2 {
public static void main(String[] args) {
int[] arr = new int[3];
combination(arr, 0, 3, 2, 0);
}
public static void combination(int[] arr, int index, int n, int r, int target) {
if (r == 0)
print(arr, index);
else if (target == n)
return;
else {
arr[index] = target;
combination(arr, index + 1, n, r - 1, target + 1);
combination(arr, index, n, r, target + 1);
}
}
//배열 출력
public static void print(int[] arr, int length) {
for (int i = 0; i < length; i++)
System.out.print(arr[i] + " ");
System.out.println("");
}
}
코멘트
구현하는 2-1, 2-2, 2-3번은 원리가 똑같은 다 비슷한 코드이다.
정리하면서 여러 가지 방법들을 써놓은 것이다.
그래서 세 개다 비슷한 말을 좀 다르게 하는 것인데,
나는 이렇게 3개의 다른 코드들을 적어보고 디버그 해보면서 조합에 대해 더 확실히 알 수 있어서 이렇게 정리한다!
연습문제
GITHUB
github.com/KwonMinha/Algorithm/blob/master/Permutaion_Combination/src/Combination.java
KwonMinha/Algorithm
Contribute to KwonMinha/Algorithm development by creating an account on GitHub.
github.com
관련 포스트
[Java] 순열 Permutation
추천 포스트
Java로 작성된 조합, 중복 조합, 순열, 중복 순열과 관련된 포스트이다.
LinkedList 사용해 구현되었고 리스트 안에 n까지 값이 순서대로 주어진다.
예를 들어 input : 3 2 라면
(0, 1, 2) 3개의 리스트가 생성되고, 그중 2개를 뽑아 조합, 중복 조합, 순열, 중복 순열을 만든다.
limkydev.tistory.com/178 [[Java] 조합, 중복 조합, 순열, 중복순열 소스]
import java.util.LinkedList;
import java.util.Scanner;
public class PerComb {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //숫자 개수
int r = sc.nextInt(); //뽑을 개수
System.out.println("원소 개수 : " + n + ", 뽑을 개수 : " + r);
System.out.print("( ");
for(int i = 0; i < n; i++) {
System.out.print(i + " ");
}
System.out.println(")");
//순열 (순서있게 배열)
System.out.println("\n순열");
LinkedList<Integer> perArr = new LinkedList<Integer>();
int[] perCheck = new int[n];
permutation(n, r, perArr, perCheck);
//중복순열 (순서있게 배열 + 자기 자신도 포함)
System.out.println("\n중복순열");
LinkedList<Integer> rePerArr = new LinkedList<Integer>();
rePermutation(n, r, perArr);
//조합 (순서 관심 없고 뽑은 유무만 생각)
System.out.println("\n조합");
int[] comArr = new int[r];
combination(comArr, n, r, 0, 0);
//중복 조합 (순서 관심 없고 뽑은 유무만 생각 + 자기 자신도 포함)
System.out.println("\n중복조합");
int[] reComArr = new int[r];
reCombination(reComArr, n, r, 0, 0);
}
//순열(순서있게 배열)
private static void permutation(int n, int r, LinkedList<Integer> perArr, int[] perCheck) {
if(perArr.size() == r){
for(int i : perArr){
System.out.print(i+" ");
}
System.out.println();
return;
}
for(int i=0; i<n; i++){
if(perCheck[i] == 0){
perArr.add(i); //값을 넣는 부분
perCheck[i] = 1;
permutation(n, r, perArr, perCheck);
perCheck[i] = 0;
perArr.removeLast();
}
}
}
//중복순열 (순서있게 배열 + 자기 자신도 포함)
private static void rePermutation(int n, int r, LinkedList<Integer> rePerArr) {
if(rePerArr.size() == r){
for(int i : rePerArr){
System.out.print(i+" ");
}
System.out.println();
return;
}
for(int i=0; i<n; i++){
rePerArr.add(i);
rePermutation(n, r, rePerArr);
rePerArr.removeLast();
}
}
//조합 (순서 관심 없고 뽑은 유무만 생각)
private static void combination(int[] comArr, int n, int r, int index, int target) {
if(r==0){
for(int i : comArr){
System.out.print(i+" ");
}
System.out.println();
return;
}
if(target == n)return;
comArr[index] = target;
combination(comArr, n, r-1, index+1, target+1); //뽑는 경우
combination(comArr, n, r, index, target+1); //안 뽑는 경우
}
//중복 조합 (순서 관심 없고 뽑은 유무만 생각 + 자기 자신도 포함)
private static void reCombination(int[] reComArr, int n, int r, int index, int target) {
if(r==0){
for(int i : reComArr){
System.out.print(i+" ");
}
System.out.println();
return;
}
if(target == n)return;
reComArr[index] = target;
reCombination(reComArr, n, r-1, index+1, target);//뽑는 경우
reCombination(reComArr, n, r, index, target+1);//안 뽑는 경우
}
}참고
[조합 Combination (Java)]
gorakgarak.tistory.com/523 [조합 Combination 알고리즘]
woongsios.tistory.com/179 [Combination 조합]
'Algorithm' 카테고리의 다른 글
| [C & Java] 트리 Tree 1 - 트리? / 이진트리? / 트리 표현법 (0) | 2020.11.03 |
|---|---|
| [Java] DFS로 모든 이동 경로 구하기 (0) | 2020.09.23 |
| [Java] 순열 Permutation (0) | 2020.05.12 |
| [Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현 (1) | 2020.05.09 |
| [Java] Graph 그래프 / 인접 행렬 / 인접 리스트 (0) | 2020.05.09 |
댓글