[알고리즘] 조합 (Combination)

숩·2023년 3월 17일

Java algorithm combination 알고리즘 자바 조합

알고리즘

목록 보기

1/6

조합 (Combination)이란?

n개의 숫자 중에서 r개의 수를 순서 없이 뽑는 경우를 말한다.
예를 들어 [1, 2, 3] 이란 숫자 배열에서 2개의 수를 순서 없이 뽑으면

[1, 2][1, 3]
[2, 3]

이렇게 3가지가 나온다.
순열을 뽑았을 때 나오는 [2, 1], [3, 1], [3, 2] 등은 중복이라 제거된다.

순열은

$nCr$
$= (r! * (n-r)!)$
$= n-1Cr-1 + n-1Cr$

이런 방식으로 계산이 가능하다.
이때 2번째 방식을 사용해서 연산할 것이다. 컴퓨터로 구할 때는 간단한 재귀식을 이용한다. 어떠한 조합의 경우에도 오른쪽 조합 2가지로 쪼개진다.

원소가 1, 2, 3에서 2개를 고르는 조합이라고 치자.
(1, 2), (2, 3), (1, 3) 3가지 경우가 있다. 이는 다음과 같은 2가지로 쪼개진다.

(1, X)인 경우

(X, X)인 경우

첫 번째 경우는 1이 확정이므로, 나머지 것만 구한다. ( $n-1Cr-1$ )
두 번째 경우는 첫 번째 숫자가 1이 아닌 경우이므로, 첫 번째 숫자까지 결정한다. ( $n-1Cr$ )

이 두 가지 경우를 더하면, 최종적으로 $nCr$ 이 완성된다.

조합을 구하는 식은 항상 저 2가지 경우로 쪼개진다.
그리고 $n-1Cr-1$ 을 구하는 2가지 경우는 $n-2Cr-1$ 와 $n-2Cr-2$ 경우로 쪼개진다. 최종적으로 쪼갤 경우가 없을 때가지 $nC0=1$ 계속된다.

n과 r이 같을 경우와 r이 0인 경우는 무조건 1이다!
이에 대한 사항만 처리하고, 나머지는 재귀 코딩에 맡긴다.

자바로 구현하기

배열을 처음부터 마지막까지 돌며
1. 현재 인덱스를 선택하는 경우
2. 현재 인덱스를 선택하지 않는 경우

이렇게 2가지로 모든 경우를 완전탐색 하면 된다!

변수	설명
`arr`	조합을 뽑아낼 배열
`output`	조합에 뽑혔는지 체크하는 배열
`n`	배열의 길이
`r`	조합의 길이

순열과 달리 조합은 r을 유지할 필요가 없으므로 숫자를 하나 뽑을 때마다 r을 하나씩 줄여준다.

r==0 일 때가 r개의 숫자를 뽑은 경우이다.

1. 백트래킹 이용하여 구현

start 변수는 기준이다.
start 인덱스를 기준으로 start 보다 작으면 뽑을 후보에서 제외, start보다 크면 뽑을 후보가 된다.

에를 들어, [1, 2, 3] 배열이 있고 start가 0부터 시작한다.
함수에 들어오면 먼저 i가 start부터 시작하는 for문에 들어간다.
만약, 0 인덱스인 1을 뽑는다면, visited[i]는 true가 되고 뽑지 않는다면 visited[i]는 false이다.

1을 선택한 경우 / 선택하지 않은 경우 둘 다 봐야 한다.
하지만 1은 이미 고려했으므로, 다음 for문은 무조건 i+1부터 시작한다.
(순열은 순서를 고려하지 않기 때문!)

Java Code

// 1. 백트래킹 구현 
// 사용 예시 : combination(int[] arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
	if(r == 0) {
		print(arr, visited, n);
		return;
	}
		
	for(int i = start; i < n; i++) {
		visited[i] = true;
		combination(arr, visited, i + 1, n, r - 1);
		visited[i] = false;
	}
}

결과

4개 중에서1개 뽑기
1 
2 
3 
4 

4개 중에서2개 뽑기
1 2 
1 3 
1 4 
2 3 
2 4 
3 4 

4개 중에서3개 뽑기
1 2 3 
1 2 4 
1 3 4 
2 3 4 

4개 중에서4개 뽑기
1 2 3 4

재귀 이용하여 구현

depth 변수를 사용한다.
depth 변수는 현재 인덱스라고 생각한다.
현재 인덱스를 뽑는다면, visited[depth] = true 로 설정
뽑지 않는다면, visited[depth] = false 로 설정

마찬가지로, 뽑은 경우 / 뽑지 않은 경우 둘 다 확인한다.
그때 이전에 본 값들은 더이상 고려 대상이 아니다. depth는 무조건 1씩 증가!

depth == 5가 되면 모든 인덱스를 확인했으므로 재귀 종료.

Java Code

// 2. 재귀 사용
// 사용 예시 : comb(arr, visited, 0, n, r)
static void comb(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;
	comb(arr, visited, depth + 1, n, r-1);
	comb(arr, visited, depth + 1, n, r);
}

결과

4개 중에서1개 뽑기
1 
2 
3 
4 

4개 중에서2개 뽑기
1 2 
1 3 
1 4 
2 3 
2 4 
3 4 

4개 중에서3개 뽑기
1 2 3 
1 2 4 
1 3 4 
2 3 4 

4개 중에서4개 뽑기
1 2 3 4

어느 쪽이든 성능 차이는 없다.

전체 코드

package Permutation_Combination;

public class Combination {
	
	// 1. 백트래킹 구현 
	// 사용 예시 : combination(int[] arr, visited, 0, n, r)
	static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
		if(r == 0) {
			print(arr, visited, n);
			return;
		}
		
		for(int i = start; i < n; i++) {
			visited[i] = true;
			combination(arr, visited, i + 1, n, r - 1);
			visited[i] = false;
		}
	}
	
	// 2. 재귀 사용
	// 사용 예시 : comb(arr, visited, 0, n, r)
	static void comb(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;
		comb(arr, visited, depth + 1, n, r-1);
		
		visited[depth] = false;	// 빼먹지 않기!
		comb(arr, visited, depth + 1, n, r);
	}
	
	public static void main(String[] args) {
		int n = 4;
		int[] arr = {1, 2, 3, 4};
		boolean[] visited = new boolean[n];
		
		for(int i = 1; i <= n; i++) {
			System.out.println("\n" + n + "개 중에서" + i + "개 뽑기");
			comb(arr, visited, 0, n, i);
		}
		
		for(int i = 1; i <= n; i++) {
			System.out.println("\n" + n + "개 중에서" + i + "개 뽑기");
			combination(arr, visited, 0, n, i);
		}
	}
	
	// 배열 출력
	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();
	}
}