완전 탐색(Exhaustive Search)

1. 완전 탐색(Exhaustive Search)이란?

완전 탐색이란 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해 보고 확인하는 기법이다. 모든 경우의 수를 고려하기 때문에 수행 속도는 느리지만, 해답을 보장한다는 특징이 있다. 경우의 수가 상대적으로 작은 경우에 고려해 볼 만한 풀이 방법이다.

---

2. 완전 탐색의 종류

• 브루트 포스 (Brute Force)
• 재귀 함수 (Recursive Function)
• 순열, 조합 (Permutation, Combination)
• 비트 마스크 (Bitmask)
• DFS/BFS
• 백트래킹 (Backtracking)

---

3. 순열, 조합, 부분집합

☑️ 순열 (Permutation)

• 서로 다른 n개의 원소 중 r개를 뽑아서 한 줄로 나열하는 경우의 수. (순서 의미 O)
• 공식
  • $_nP_r=\frac{n!}{(n-r)!}=n \times (n-1) \times (n-2)....$
  • $_nP_n=n!$
• 시간 복잡도: $O(n!)$

☑️ 조합(Combination)

• 서로 다른 n개의 원소 중 r개를 순서 없이 골라내는 경우의 수. (순서 의미 X)
• 공식
  • $_nC_r=\frac{n!}{(n-r)! \times r!}$
  • $_nC_0=_nC_n=1$
  • $_nC_r = _{n-1}C _r+_{n-1}C_{r-1}$

☑️ 부분 집합(Power set)

• 어떤 집합의 일부 원소로 이루어진 집합.
• 배낭문제(Knapsack) 와 같이 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것이다.
• 시간 복잡도: $O(2^n)$
  • 각 원소를 포함시키거나 포함시키지 않는 두가지 경우의 수가 있기 때문

---

4. 예제 코드

📌 N개의 주사위를 던져서 순열, 중복 순열, 조합, 중복 조합 중 선택하여 나올 수 있는 모든 경우의 수 계산

import java.io.*;
import java.util.*;

public class Main {
	static int N; 			// 던지는 주사위 수
	static int[] numbers; 	// 각각의 주사위의 눈
	static int totalCnt; 	// 경우의 수
	static boolean[] isSelected;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(in.readLine()," ");
		int mode=Integer.parseInt(st.nextToken());
		N=Integer.parseInt(st.nextToken());
		
		numbers=new int[N];
		
		switch(mode) {
		case 1:
			isSelected=new boolean[7];
			permutation1(0);  // 1. 순열 호출
			System.out.println("총 경우의수: "+totalCnt);
			break;
		case 2:	
			permutation2(0);  // 2. 중복 순열 호출
			System.out.println("총 경우의수: "+totalCnt);
			break;	
		case 3:
			combination1(0,1); // 3. 조합 호출
			System.out.println("총 경우의수: "+totalCnt);
			break;
		case 4: // 중복 조합
			combination2(0,1); // 4. 중복 조합 호출
			System.out.println("총 경우의수: "+totalCnt);
			break;
		}	
	}
	
	// 순열
	private static void permutation1(int cnt) {
		// 기저 조건
		if(cnt==N) { 
			System.out.println(Arrays.toString(numbers));
			totalCnt++;
			return;
		}
		// 유도 파트
		for(int i=1;i<=6;i++) {
			if(isSelected[i]) continue;
			numbers[cnt]=i;
			isSelected[i]=true;
			permutation1(cnt+1);
			isSelected[i]=false;
		}
	}
	
	// 중복 순열
	private static void permutation2(int cnt) {
		// 기저 조건
		if(cnt==N) {
			System.out.println(Arrays.toString(numbers));
			totalCnt++;
			return;
		}
		// 유도 파트
		for(int i=1;i<=6;i++) {
			numbers[cnt]=i;
			permutation2(cnt+1);
		}
	}
	
	// 조합
	private static void combination1(int cnt, int start) { 
		// 기저 조건
		if(cnt==N) {
			System.out.println(Arrays.toString(numbers));
			totalCnt++;
			return;
		}
		// 유도 파트
		for(int i=start;i<=6;i++) {
			numbers[cnt]=i;
			combination1(cnt+1,i+1);
		}
	}
	
	// 중복 조합
	private static void combination2(int cnt, int start) { 
		// 기저 조건
		if(cnt==N) {
			System.out.println(Arrays.toString(numbers));
			totalCnt++;
			return;
		}
		// 유도 파트
		for(int i=start;i<=6;i++) {
			numbers[cnt]=i;
			combination2(cnt+1,i);
		}
	}
}