[Algorithm] 완전탐색 - 조합

조합이란 ?

조합이란 서로 다른 n개의 원소 중 r개를 순서 없이 일렬로 나열하는 경우의 수이다.

 

예) 주사위를 2번 던졌을 때 서로 다른 숫자가 순서 상관없이 조합할 수 있는 경우의 수 

---

조합 특징 ?

 

• 조합은 선택에 중복 없이 순서 상관없이 결과를 가져온다.
• 매 자리마다 이전 원소의 다음 원소부터 확인한다.
• 대표적인 구현 방법은 재귀 구현이다.
• 재귀의 깊이는 선택된 원소의 개수와 일치한다.

---

조합 구현 순서 ?

재귀 호출 시 현재 깊이 정도 (원소 선택 현황)과 탐색을 시작할 인덱스 값을 잘 확인하며 아래를 수행하자.

 

1. 재귀를 호출하며, 깊이 정도와 탐색을 시작할 인덱스 값을 넘겨준다.
2. 깊이 정도로 원소를 다 선택했는지 확인한다.
3. 원소를 다 선택했다면 원하는 동작 후 메서드를 종료한다.
4. 덜 선택한 경우 전달받은 인덱스 값부터 탐색한다.
5. 1번 ~ 4번 과정을 반복한다.

---

조합 시간복잡도

순열과 비슷하나 재귀를 호출할 때마다 확인해야하는 원소가 줄어든다.

 

조합의 시간복잡도 : O(2^n)

---

조합 그림으로 살펴보기

[ 주사위의 모습 ]

[ 1, 1 ] [ 1, 2 ] [ 1, 3 ] [ 1, 4 ] [ 1, 5 ] [ 1, 6 ]

 

[ 2, 1 ] [ 2, 2 ] [ 2, 3 ] [ 2, 4 ] [ 2, 5 ] [ 2, 6 ]

. . .

[ 5, 1 ] [ 5, 2 ] [ 5, 3 ] [ 5, 4 ] [ 5, 5 ] [ 5, 6 ]

 

[ 6, 1 ] [ 6, 2 ] [ 6, 3 ] [ 6, 4 ] [ 6, 5 ] [ 6, 6 ]

---

소스코드

import java.util.Arrays;
import java.util.Scanner;

public class OverlapCombination {
	
	// 주사위 던지는 횟수, 주사위 던지기 모드
	public static int throwCnt, throwMode;
	// 던져진 주사위 결과 배열
	public static int nums[];
	
	// 주사위 던지기 메서드 (중복 조합 버전)
	static void throwDiceOverlapCombination(int idx, int cnt) {
		
		// 종료 조건 : 주사위를 다 던진 경우
		if(cnt==throwCnt) {
			
			// 결과 출력
			System.out.println("중복 조합 : " + Arrays.toString(nums));
			return;
		}
		
		// 한 번 던질 때 가능한 상황에 대한 시도(idx ~ 6 중 하나)
		for(int i=idx; i<=6; i++) {
			
			// 주사위 결과 번호 저장
			nums[cnt] = i;
			
			// 다음 주사위 던지기
			throwDiceOverlapCombination(i, cnt+1);
		}
	}
	
	// 주사위 던지기 메서드 (조합 버전)
	static void throwDiceCombination(int idx, int cnt) {
		
		// 종료 조건 : 주사위를 다 던진 경우
		if(cnt==throwCnt) {
			
			// 결과 출력
			System.out.println("조합 : " + Arrays.toString(nums));
			return;
		}
		
		// 한 번 던질 때 가능한 상황에 대한 시도(idx ~ 6 중 하나)
		for(int i=idx; i<=6; i++) {
			
			// 주사위 결과 번호 저장
			nums[cnt] = i;
			
			// 다음 주사위 던지기
			throwDiceCombination(i+1, cnt+1);
		}
	}
	
	public static void main(String[] args) {
		
		// 입력으로 주사위 던지는 횟수, 주사위 던지기 모드(1,2)
		Scanner sc = new Scanner(System.in);
		
		// 주사위 던지는 횟수 입력
		throwCnt = sc.nextInt();
		
		// 주사위 던지기 모드 입력
		throwMode = sc.nextInt();
		
		// 던져진 주사위 결과 배열 생성
		nums = new int[throwCnt];

		switch(throwMode) {
		
		// 중복 조합
		case 1:
			// 주사위 던지기 (중복 조합 버전)
			throwDiceOverlapCombination(1,0);
			break;
			
		// 조합
		case 2:
			
			// 주사위 던지기 (조합 버전)
			throwDiceCombination(1,0);
			break;
		}
	}
}

---

요약

• 조합은 선택에 중복 없이 순서 상관없이 결과를 가져온다.
• 매 자리마다 이전 원소의 다음 원소부터 확인한다.
• 대표적인 구현 방법은 재귀 구현이다.
• 재귀의 깊이는 선택된 원소의 개수와 일치한다.
• 조합의 시간복잡도는  O(2^n) 이다.