완전검색 - 1

완전 검색

모든 경우에 대해서 검색하는 방법

부분집합

• 주어진 집합의 원소 중 일부 또는 전체를 포함하는 집합
• 공집합(아무것도 없는) 또한 부분집합의 일부가 된다.
• 집합의 원소가 N개일 때, 부분 집합의 수는 2N개가 된다.
• 부분 집합의 구현

static String[] element = {"단무지", "햄", "오이", "시금치"};
static int N = 4;
static int[] sel = new int[N]; // 해당 인덱스의 재료를 사용 유무 저장 배열 
	
public static void main(String[] args) {
	// 재료가 4개라면, 반복문이 4개가 필요하다. 
	for(int i = 0; i <= 1; i++) { // 단무지를 위한 반복문 
		sel[0] = i; 
		for(int j = 0; j <= 1; j++) { // 햄을 위한 반복문 
			sel[1] = j;
			for(int k = 0; k <= 1; k++) { // 오이를 위한 반복문 
				sel[2] = k;
				for(int l = 0; l <= 1; l++) { // 시금치를 위한 반복문 
					sel[3] = l;
					System.out.println(Arrays.toString(sel));
				}
			}
		}
	}
}

• 비트로 보게 된다면 1<<N이 된다.

static String[] element = {"단무지", "햄", "오이", "시금치"};
static int N = 4;
static int[] sel = new int[N]; // 해당 인덱스의 재료를 사용 유무 저장 배열 
	
public static void main(String[] args) {
		
	// 모든 김밥의 가짓수를 확인하기 위한 for문으로, 2의 N승만큼 돌게 된다. 
	// i의 경우, 하나의 김밥 종류라고 생각하게 되어야 한다. 
	for(int i = 0 ; i < (i<<N); i++) {
		String temp = "";
			
		// 김밥 종류에 따라, 재료를 확인하는 방법 
		for(int j = 0; j < N; j++) {
			if( (i & (1 << j)) > 0) { // 해당 재료의 여부를 확인하기 위해 
				temp += element[j];
			}
		} // 재료 확인이 끝
		System.out.println(temp);
	}
}

• 재귀 함수로 인한 부분 집합 구현

public class classroom_2 { // 재귀 함수

	static String[] element = {"단무지", "햄", "오이", "시금치"};
	static int N;
	static boolean[] sel; // 해당 인덱스의 재료를 사용 유무 저장 배열 
	
	public static void main(String[] args) {
		
		N = 4;
		sel = new boolean[N];
		
		powerset(0);

	}
	
	// N은 이미 static 하므로, 들고 다닐 필요가 없다. 
	// idx의 경우 내가 어떤 재료를 선택할 지에 대한 인덱스이다. 
	public static void powerset(int idx) {
		// 기저 조건 base case -> 재귀를 빠져나가는 조건 
		// idx 가 더는 판단할 재료가 없을 때 (+1한 것이 size와 동일하다) 
		if (idx >= N) {
			String temp = "김밥 재료 : ";
			for(int i = 0; i < N; i++) {
				if(sel[i]) temp += element[i];
			}
			System.out.println(temp);
			return;
		}
		
		
		// 재귀 부분
		// 재료를 사용한 경우 
		sel[idx] = true; 
		powerset(idx + 1);
		
		sel[idx] = false;
		powerset(idx + 1);
	}
}

조합

• 활용할 수 있는 재료를 2개 이상을 사용하여 하나를 완성하는 경우.
• 순서에 상관 없이, 주어진 집합에서 일부 원소를 선택하는 방법의 수
• 서로 다른 n개의 원소를 가지는 집합에서 r개를 뽑아, 나열하는 경우 다음과 같이 표현 가능하다.

public class classroom_3 {
	static String[] element = {"상추", "패티", "치즈", "토마토"};

	
	static int N, R; // N : 재료의 수, R : 내가 뽑고 싶은 재료의 수 
	static String[] sel; // 뽑은 재료를 저장할 배열 
	
	public static void main(String[] args) {
		N = element.length;
		R = 2;
		
		sel = new String[R];
		
		combination(0, 0);
	}
	
	// idx : 재료의 인덱스 
	// sidx : 내가 뽑은 재료의 인덱스 (저장이 될 sel의 인덱스) 
	public static void combination(int idx, int sidx) {
		// 기저 조건
		if (sidx == R) {
			System.out.println(Arrays.toString(sel));
			return;
		}
		
		// 어차피 위에서 완벽한 햄버거가 다 걸리기 때문에, 
		// 이 조건은 완벽하지 않은 햄버거만 나온다. 
		if (idx == N) { 
			return;
		}
		
		// 재귀 부분 
		sel[sidx] = element[idx]; 
		combination(idx+1, sidx+1);
		
		combination(idx+1, sidx); // 실제 재료를 아직 뽑지 않았을 때 
	}
}

• 재귀함수 + 반복문을 이용해서도 풀 수 있다.
• 원소의 갯수가 정해져 있어야 하는 제한과 뽑아야 하는 원소의 갯수만큼 for문을 사용해주면 되는 반복문의 복잡함을 해소하기 위해.

public static void combination(int idx, int sidx) {
	// 기저 조건
	if (sidx == R) {
		System.out.println(Arrays.toString(sel));
		return;
	}
		
	// 이미 범위를 정해두고, 반복문을 돌리기 때문에 범위를 벗어나는 건 걱정하지 않아도 된다. 
	// i < N - R + sidx : 어떠한 깊이에서, 마지막 노선을 계산하는 방식이다. 
	for(int i = idx; i <= N - R + sidx; i++) {
		sel[sidx] = element[i];
		combination(i+1, sidx+1);
	}
}