완전탐색 - 순열, 조합, 부분 집합

• 생각할 수 있는 모든 경우의 수를 구하다. 
• 상대적으로 빠른 시간에 문제 해결을 할 수 있다.
• Brute-force 또는 Generate - and - test 기법이다.

  ---

순열(Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열 : nPr = n*(n-1)*(n-2)*---*(n-r+1)
• 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련
• N개의 요소들에 대해서 N!개의 순열들이 존재

 

• 알고리즘

n개 숫자에 대해서 시도, 앞에서 선택된 수는 배제, 해당 개수의 수 선택

import java.util.Scanner;

public class Permutation {
	
	static int[] numbers, result; // 숫자들의 배열, 결과를 담을 배열 
	static boolean[] check; //방문 여부를 확인하는 배열
	static int n, r; //전체 n개 중, r개를 선택

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		r = scanner.nextInt();
		//numbers값도 채우고 등등
		perm(0);

	}
	
	//cnt: 현재 몇개 까지 선택했는지를 나타냄.
	private static void perm(int cnt) {
		if(cnt == r) {//r개를 모두 다 선택했다면 재귀함수를 종료
			//이 안에서 조합의 경우를 가지고 하고싶은거 다해~
			return; 
		}
		
		for(int i = 0; i<numbers.length; i++) {
			if(check[i]) continue; //이미 선택했다면 그만
			result[cnt] = numbers[i]; //결과에 numbers[i]를 넣음(혹은 그냥 인덱스만 넣어도 된다)
			check[i] = true; //방문 처리를 한다. 
			perm(cnt+1); // 재귀적으로 그 다음을 부른다.
			check[i] = false; //재귀 함수가 끝나면 또 다른 재귀에서 사용해야 하니 false로 바꾼다(반납) 
		}
		
	}

}

 

---

조합(Combination)

• 서로 다른 n개 중 r개를 순서 없이 뽑는다.
• nCr =  nPr / r! = n*(n-1)*(n-2)*---*(n-r+1) / r*(r-1)*(r-2)*(r-3)*---2*1

• 알고리즘

n개의 숫자 중, r개를 선택한다. 그때, 중복을 제거하기 위해 나 이후 것만 선택한다. 

import java.util.Scanner;

public class Combination {
	
	static int[] numbers, result; // 숫자들의 배열, 결과를 담을 배열 
	static int n, r; //전체 n개 중, r개를 선택

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		r = scanner.nextInt();
		//numbers값도 채우고 등등
		comb(0,0);

	}
	
	//cnt: 현재 몇개 까지 선택했는지를 나타냄.
	//start: 시작 인덱스를 나타냄. 방문 여부 확인을 안하고 그냥 뒤에부터 선택하기 위해서
	private static void comb(int cnt, int start) {
		if(cnt == r) {//원하는 개수 만큼 뽑았다면
			//하고싶은거 다해
			return; 
		}
		
		for(int i = start; i<numbers.length; i++) {
			result[cnt] = numbers[i]; // 직접 값을 넣어도 되고, 아니면 인덱스만 넣어도 된다.
			comb(cnt+1, i); //선택한 개수(cnt)를 하나 증가, start는 나 부터 시작
			
		}
		
	}

}

---

부분 집합(Subset)

• 한 원소에 대해서 포함을 하거나(선택을 하거나), 포함을 하지 않는다(선택을 하지 않는다).
• 즉, 한 원소 당 2가지의 경우의 수가 있다.
• 집합에 포함된 원소들을 선택하는 것
• 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것

 

• 알고리즘

한 원소에 대해서 이를 포함 하거나, 포함하지 않는 경우 모두를 생각한다. 

import java.util.Scanner;

public class Subset {
	
	static int[] numbers; // 숫자들의 배열
	static boolean[] check; //방문했는가를 체크하는 배열, numbers와 같은 크기(부분신 느낌)
	static int n; //전체 n개

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
	
		//numbers값도 채우고 등등
		

	}
	
	//cnt: 현재 몇개 까지 뽑을 지, 안뽑을지 결정했는지를 나타냄.
	private static void subset(int cnt) {
		if(cnt == n) {//전체 원소의 개수 만큼 결정했다면
			
			for(int i = 0; i<check.length; i++) {
				if(check[i]) {//포함된 것들만 뽑는다. - subset들
					//여기서 생성된 subset들 가지고 하고싶은거 다해!!
				}
			}
			
			return; 
		}
		//해당 원소는 포함하는 경우
		check[cnt] = true;
		subset(cnt+1);
		
		//해당원소는 포함하지 않는 경우
		check[cnt] = false;
		subset(cnt+1);
		
		
		
	}

}