완전 탐색 - swkim0128/PARA GitHub Wiki

완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법.

Brute-force 혹은 generate-and-test 기법이라고도 불리 운다.

모든 경우의 수를 테스트한 후, 최종 해법을 도출한다.

상대적으로 빠른 시간에 문제 해결(알고리즘 설계)을 할 수 있다.

일반적으로 경우의 수가 상대적으로 작을 때 유용한다.

모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.

검정 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.

또한, 이들은 전형적으로 순열(permutation), 조합(combination), 그리고 부분집합(subsets)과 같은 조합적 문제들(Combinational Problems)과 연관된다.

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

• 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현한다.
  nPr

• 그리고 nPr은 다음과 같이 식이 성립한다.
  nPr = n * (n - 1) * (n - 2) * ... * (n - r + 1)

• nPn = n!이라고도 표기하며 Factorial이라 부른다.
  n! = n * (n - 1) * (n - 2) * ... * 2 * 1

순열을 생성하는 방법

재귀 호출을 통한 순열 생성 - boolean[] 사용

input[] : 숫자 배열
numbers[] : 순열 저장 배열
isSelected[] : 인덱스 해당하는 숫자가 사용 중인지 저장하는 배열
perm(cnt)  // cnt : 현재까지 뽑은 순열 원소의 개수
	if cnt == N
		순열 생성 완료
	else
		for i from 0 to N - 1
			if isSelected[i] == true then continue
			numbers[cnt] <- input[i]
			isSelected[i] <- true
			perm(cnt + 1)
			isSelected[i] <- false
		end for
end perm()

비트마스킹을 통한 순열 생성 - 비트연산자를 사용

input[] : 숫자 배열
numbers[] : 순열 저장 배열

perm(cnt, flag)  
// cnt : 현재까지 뽑은 순열 원소의 개수, flag : 선택된 원소에 대한 비트정보를 표현하는 정수
	if cnt == N
		순열 생성 완료
	else
		for i from 0 to N - 1
			if (flag & 1 << i) != 0 then continue
			numbers[cnt] <- input[i]
			perm(cnt + 1 flag | 1 << i)
		end for
end perm()

현 순열에서 사전 순으로 다음 순열 생성 - NextPermutation

알고리즘

배열을 오름차순으로 정렬한 후 시작한다.
아래 과정을 반복하여 사전순으로 다음 큰 순열 생성(가장 큰 내림차순 순열을 만들 때까지 반복한다.)

1. 뒤쪽부터 탐색하여 교환위치(i - 1) 찾기(i : 꼭대기)
2. 뒤쪽부터 탐색하며 교환위치(i - 1)와 교환활 큰 값 위치(j)찾기
3. 두 위치 값(i - 1, j) 교환
4. 꼭대기위치(i)부터 맨 뒤까지 오름차순 정렬

주의사항

NextPermutation 사용 전에 숫자배열을 오름차순으로 정렬하여 가장 작은 순열 한번 처리

nb(int[] numbers) {
	int N = numbers.length;

	int i = N - 1;
	while (i > 0 && numbers[i - 1] >= numbers[i])
		i--;

	if (i == 0)
		return false;

	int j = N - 1;
	while (numbers[i - 1] >= numbers[j])
		j--;

	swap(numbers, i - 1, j);

	int k = N - 1;
	while(i < k) {
		swap(i - 1, k);
		i++;
		k--;
	}

	return true;
}	

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합(combination)이라고 부른다.

재귀 호출을 이용한 조합 생성 알고리즘

input[] : n개의 원소를 가지고 있는 배열
numbers[] : r개의 크기의 배열, 조합이 저장될 배열

comb(cnt, start)  
// cnt : 현재까지 뽑은 조합 원소 개수, start : 조합 시도할 원소의 시작 인덱스

	if cnt == r
		조합 생성 완료
	else
		for i from start to n - 1
			numbers[cnt] <- input[i];
			comb(cnt + 1, i + 1);
		end for
end comb()

NextPermutation 활용

원소크기와 같은 크기의 int 배열 P를 생성하여 r개 크기만큼 뒤에서 0이 아닌 값(에를 들어 1)으로 초기화한다.

nextPermutation 알고리즘을 활용한다.

nextPermutation 알고리즘 한 번 수행시마다 조합이 만들어짐
→ nextPermutation 과정 수행 시마다 0이 아닌 값의 위치가 변경됨

P 배열에서 0이 아닌 값을 갖고 있는 위치에 해당하는 원소가 조합에 선택된 것

집합에 포함된 원소들을 선택하는 것이다.

다수의 중요 알고리즘들이 원소들의 그훕에서 최적의 부분 집합을 찾는 것이다.

N개의 원소를 포함한 집합

자기 자신과 공집합 포함한 모든 부분집합(power set)의 개수는 2의 n제곱 개

원소의 수가 증가하면 부분집합의 개수는 지수적으로 증가

재귀적 구현을 통해 생성하는 방법

각 원소를 부분집합에 포함 / 비포함의 형태로 재귀적 구현을 함.

input[] : 숫자 배열
isSelected[] : 부분집합에 선택 / 미선택 여부를 저장한 배열
generateSubset(cnt)  // cnt : 현재까지 처리한 원소개수
	if (cnt == N)
		부분 집합 완성
	else
		isSelected[cnt] <- true
		generateSubSet(cnt + 1)
		isSelected[cnt] <- false
		generateSubSet(cnt + 1)
end generateSubSet()

바이너리 카운팅을 통한 사전적 순서(Lexicographical Order)로 생성하는 방법

부분집합을 생성하기 위한 가장 자연스러운 방법이다.

바이너리 카운팅(Binary Counting)은 사전적 순서로 생성하기 위한 가장 간단한 방법이다.

int arr[] = {3, 6, 7, 1, 5, 4};
int n = arr.length;

for (int i = 0; i < (1 << n); i++) {
	for (int j = 0; j < n; j++) {
		if (i & (1 << j) != 0) {
			System.out.print(arr[j] + " ");
		}
	}
	System.out.println();
}