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

완전 탐색 - 순열

순열(Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열은 nPr
• nPr은 다음과 같은 식 성립
  • nPr = n * (n-1) * (n-2) * ... *(n-r+1)
• N 개의 요소들에 대해서 n! 개의 순열들이 존재
  • n > 12 인 경우, 시간 복잡도 폭발적 증가

순열 구현

	// 현재 자리의 수 뽑기
	public static void permutation(int cnt) {
		
		if(cnt==R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		// 입력받은 모든 수를 현재 자리에 넣어보기
		for (int i = 0; i < N; i++) {
			// 기존자리의 수들과 중복되는지 체크
			if(isSelected[i]) {
				continue;
			} else {
				numbers[cnt] = input[i];
				isSelected[i] = true;
				// 다음 수 뽑으러 가기
				permutation(cnt+1);
				isSelected[i] = false;
			}
		}
	}

완전 탐색 - 조합

조합(Combination)

• 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합
• nCr

조합 구현

	public static void combination(int cnt, int start) {
		
		if(cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = start; i < N; i++) {
			numbers[cnt] = input[i];
			combination(cnt+1, i+1); // 다음자리는 현재 뽑은 i의 다음수부터 시작하도록 전달
		}
	}

완전 탐색 - 부분 집합

부분 집합

• 집합에 포함된 원소들을 선택하는 것
• 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것.
  • ex) 배낭 짐싸기
• 부분집합의 수
  • 집합의 원수가 n개일 때, 공집합을 포함한 부분집합의 개수는 22개이다.
  • 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.

부분 집합 구현

	public static void generateSubset(int cnt) {	// 부분 집합에 고려해야 하는 원소, 직전까지 고려한 원소 수
		
		if(cnt==N) {	// 마지막 원소까지 부분집합에 다 고려된 상황
			
			for(int i=0; i<N; i++) {
				System.out.print((isSelected[i]?input[i]:"X")+"  ");
			}
			System.out.println();
			return;
		}
		
		// 현재 원소를 선택
		isSelected[cnt] = true;
		generateSubset(cnt+1);
		// 현재 원소를 비선택
		isSelected[cnt] = false;
		generateSubset(cnt+1);
	}

부분 집합의 합 문제

• 유한개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내는 문제
• 예를 들어, {-7, -3, -2, 5, 8}라는 집합이 있을 때, {-3, -2, 5}는 이 집합의 부분집합이면서 (-3)+(-2)+5=0이므로 이 경우의 답은 참이 된다.
• 완전검색 기법으로 부분집합 합 문제를 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야 한다.