[알고리즘 이론] 완전 탐색 - 조합

완전 탐색 알고리즘

1. 순열
2. 조합
3. 부분집합

📌 Combination

• 서로 다른 것n개의 원소 중 r개를 순서 없이 골라 나열 한 것
  
  

시간복잡도

조합 공식 : $_nC_r = \frac {n!} {(n - r)!r!}$ $(n\leq r)$
중복 조합 공식 : $_nH_r = _{n+r-1} C _{r}$

조합의 시간복잡도는 n값에 대한 모든 경우의 수를 구했을 때, $_nC_n = 2^N$
즉, $O(2^n)$의 시간 복잡도를 가짐

😱 $_N C _r \leq _{30}C_{15}$ 의 조건이 만족할 때만 완전탐색을 쓰자

$O(2^n)$
2^20 = 104만
2^22 = 419만
2^24 = 1677만

n값이 커질 수록 연산횟수가 급격히 증가하기 때문에 완전탐색 할때 n의 크기에 주의!

---

반복문을 이용한 조합

• 뽑는 개수가 고정되어 있을 때 사용 (뽑는 개수 = for문의 개수)

 	public class Combination_loop {

	public static void main(String[] args) {
		int[] arr = new int[] {1,2,3,4,5};
		
		// nC2 중복을 허용하는 조합
		System.out.println("중복을 허용하는 조합");
		for(int i=0;i<arr.length;i++) {
			for(int j=i;j<arr.length;j++) {
				System.out.print("{ "+arr[i]+" "+arr[j]+" }"+'\t');
			}
			System.out.println();
		}
		
		// nH2 중복을 허용하지 않는 조합
		System.out.println("중복을 허용하지 않는 조합");
		for(int i=0;i<arr.length;i++) {
			for(int j=i;j<arr.length;j++) {
				if(i!=j) {
					System.out.print("{ "+arr[i]+" "+arr[j]+" }"+'\t');
				}
			}
			System.out.println();
		}
	}

}

• 출력
  
  중복을 허용하는 조합
  { 1 1 } { 1 2 } { 1 3 } { 1 4 } { 1 5 }
  { 2 2 } { 2 3 } { 2 4 } { 2 5 }
  { 3 3 } { 3 4 } { 3 5 }
  { 4 4 } { 4 5 }
  { 5 5 }
  
  중복을 허용하지 않는 조합
  { 1 2 } { 1 3 } { 1 4 } { 1 5 }
  { 2 3 } { 2 4 } { 2 5 }
  { 3 4 } { 3 5 }
  { 4 5 }

재귀를 이용한 조합

• 한 depth에서 반복문을 시작하는 초기값을 변경 조합 구하기

public class Combination_recursive {
	
	static int[] arr = new int[] {1,2,3,4,5};
	static int[] combinationResult;
	static int r;
	
	public static void main(String[] args) {
	
		Scanner sc = new Scanner(System.in);
		r = sc.nextInt();
		combinationResult = new int[r];
		
		// 중복 조합
		CombinationDuplicate(0, 0);  // depth, start

		System.out.println();

		// 중복을 허용하지 않는 조합
		Combination(0, 0);  // depth, start
		
	}
	private static void CombinationDuplicate(int depth, int start) {
		if(depth == r) {
			System.out.println(Arrays.toString(combinationResult));
			return;
		}
		for(int i=start;i<arr.length;i++) {
			combinationResult[depth] = arr[i]; // 원소 하나 뽑기
			Combination(depth+1, i);// 다음 원소 뽑기를 다음 재귀에 넘김
		}
	}
	
	private static void Combination(int depth, int start) {
		if(depth == r) {
			System.out.println(Arrays.toString(combinationResult));
			return;
		}
		for(int i=start;i<arr.length;i++) {
			combinationResult[depth] = arr[i]; // 원소 하나 뽑기
			Combination(depth+1, i+1);// 다음 원소 뽑기를 다음 재귀에 넘김 + 중복 제거를 위해 i + 1로 다음 배열을 시작점으로 넘긴다
		}
	}
}

입력 : 2
출력 :
중복을 허용하는 조합
[1, 1][1, 2]
[1, 3][1, 4]
[1, 5][2, 2]
[2, 3][2, 4]
[2, 5][3, 3]
[3, 4][3, 5]
[4, 4][4, 5]
[5, 5]

중복을 허용하지 않는 조합
[1, 2][1, 3]
[1, 4][1, 5]
[2, 3][2, 4]
[2, 5][3, 4]
[3, 5][4, 5]

Next Permutation을 이용한 조합

• 각자리의 가능한 조합구할 수 있음
  Next Permutation 응용 - 조합 만들기