완전 검색

<완전 검색 (Exhaustive Search) >

: 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 방법
      = Brute-force = generate-and-test

• 모든 경우의 수를 테스트, 최종 해법 도출
• 상대적으로 빠른 시간에 문제 해결
• 일반적으로 경우의 수가 상대적으로 작을 때 유용
  -> 우선 완전 검색으로 접근해서 해답을 도출하고, 다른 알고리즘을 사용하여 성능 개선 및 해답 확인하기
  
  
  
  

<순열>

: 서로 다른 n개의 원소 중에서 중복을 허락하지 않고,
<br> 순서를 생각하며 r개를 일렬로 나열하는 수열이다. nPr = n!/(n-r)!

import java.util.*;

public class PermutationTest {
	static int N = 3, R = 2;
	static int[] input, numbers;
	static boolean[] isSelected; // 원소가 선택되었는지 확인하는 boolean배열

	public static void main(String[] args) {
		numbers = new int[] { 1, 2, 3 };

		// 초기화
		input = new int[R]; // 원소를 선택한 후에 담을 배열
		isSelected = new boolean[N];
		permutation(0);
	}

	private static void permutation(int cnt) {
		if (cnt == R) {
			System.out.println(Arrays.toString(input));
			return;
		}
		for (int i = 0; i < N; i++) {
			// 원소가 이미 선택되었으면
			if (isSelected[i]) continue;

			input[cnt] = numbers[i]; // 원소 넣고
			isSelected[i] = true; // 선택됨 표시
			permutation(cnt + 1); // 다음 원소 뽑으러 가기
			isSelected[i] = false;
		}
	}
}

출력 결과

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

<조합>

: 서로 다른 n개의 원소 중에서 중복을 허락하지 않고,
순서를 생각하지 않으며 r개를 뽑는 것이다.

import java.util.*;

public class CombinationTest {
	static int[] a, inputs;
	static int N = 4, R = 3;

	public static void main(String[] args) {
		a = new int[] { 1, 4, 7, 9 };
		inputs = new int[R];
		combination(0, 0);
	}

	static void combination(int cnt, int start) {
		if (cnt == R) {
			System.out.print(Arrays.toString(inputs) + "  ");
			return;
		}
		// i 시작을 start로 주기
		for (int i = start; i < N; i++) {
			inputs[cnt] = a[i];
			combination(cnt + 1, i + 1); // 지금 뽑은 거 다음 꺼부터 뽑기
		}
	}
}

출력 결과

[1, 4, 7]    [1, 4, 9]   [1, 7, 9]    [4, 7, 9]

<부분집합>

: 집합에 포함된 원소들을 선택하는 것이다.
집합의 원소가 N개일 때, 공집합을 포함한 부분집합의 수는 2^N개이다.

public class SubsetTest {
	static int N = 3;
	static int[] numbers;
	static boolean[] isSelected;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		numbers = new int[] { 1, 2, 3 };
		isSelected = new boolean[N];
		subset(0);
	}

	private static void subset(int cnt) {
		if (cnt == N) {
			sb.append("{");
			for (int i = 0; i < N; i++) {
				if (isSelected[i]) // 원소가 선택되었다면 출력
					sb.append(numbers[i]).append(", ");
			}
			//출력 보기 좋게 하려고
			if(sb.length() >= 2) sb.setLength(sb.length() - 2);
			sb.append("}");
			System.out.println(sb);
			sb.setLength(0);
			return;
		}

		isSelected[cnt] = true; // 원소 선택됨
		subset(cnt + 1); // 다음 원소 선택하러

		isSelected[cnt] = false; // 원속 선택 안 됨
		subset(cnt + 1); // 다음 원소 선택하러
	}
}

출력 결과

{1, 2, 3}
{1, 2}
{1, 3}
{1}
{2, 3}
{2}
{3}
{}