<aside> ❗ 완전탐색은 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법으로 Brute Force(브루트 포스) 라고도 부른다.

</aside>

→ 완전탐색 알고리즘을 사용하기 위해서는 다음과 같은 수행 과정을 거친다.

1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다. (효율성 테스트…)
2. 가능한 모든 방법을 다 고려한다.
3. 실제 답을 구할 수 있는지 적용한다.

이때 (2)의 모든 방법에는 다음과 같은 방법이 존재한다.

• Brute Force 기법 - 반복/조건문을 활용해 모든 케이스 테스트하는 방법
• 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
• 재귀 호출
• 비트마스크 - 2진수 표현 기법을 활용하는 방법
• BFS, DFS를 활용하는 방법 → 추후 자세하게 정리

Brute Force 기법

이 방법은 반복/조건문을 통해 가능한 모든 방법을 단순히 찾는 경우를 의미한다.

ex) 자물쇠 암호를 찾는 경우

순열(Permutation)

순열이란, 서로 다른 것들 중 몇 개를 뽑아 한 줄로 나열하는 것을 말한다.

→ N개의 서로 다른 데이터가 있다면 전체 순열의 가지 수 = N!

이러한 순열을 구현하는 로직을 생각해보자.

• 재귀함수로 표현

• 해당 인덱스에 해당하는 숫자가 이미 사용중인지 저장하고 있는 별도의 배열 필요

  → 만약 이미 뽑은 인덱스의 경우 pass

  → 뽑지 않은 인덱스면 방문처리 하고 index+1 하는 재귀함수로 들어감.

• 다음 순열을 구하는데 영향을 주지 않기 위해 방문처리를 되돌려야 함.

class Main {
	private static int n, m; // n에서 m개를 뽑아서 나열
	private static int[] arr; // 순열을 저장하는 배열
	private static boolean[] visited; // 중복을 제거하기 위한 방문 처리
	private static int tc; // 순열 개수
	
	**private static void permutation(int cnt) {
		// 원소 m개를 모두 선택했으면 출력하기 (기저 조건)
		if(cnt == m) {
			tc++;
			System.out.println(Arrays.toString(arr)); 
			return;
		}
		
		for(int i=1; i<=n; i++) { 
			// 중복 검사
			if(!visited[i]) {
				arr[cnt] = i; // 선택
				visited[i] = true; // 방문 처리
				permutation(cnt + 1); // 다음 요소 뽑기
				visited[i] = false; // 다 뽑았으면 되돌리기
			}
		}
	}**
	
	public static void main(String[] args) {
		n = 4; // 4개의 원소 중 {1, 2, 3, 4}
		m = 2; // 2개를 뽑기
		arr = new int[m];
		visited = new boolean[n + 1];
		permutation(0); // start ~
	}
}