완전 탐색
- 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
- Brute-force 혹은 generate-and-test 기법이라고도 불리움
- 일반적으로 경우의 수가 상대적으로 작을 때 유용한 기법
장점
- 모든 경우의 수를 생성하고 테스트하기 때문에, 해답을 찾아내지 못할 확률이 작다.
단점
- 모든 경우의 수를 생성하기 때문에 수행 속도가 느리다
완전 탐색 - 순열 (Permutation)
- 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
- nPr = n * (n-1) * (n-2) * ... * (n-r+1)
- nPn = n * (n-1) * ... * 2 * 1 = n!
- 순서화된 요소들의 집합에서 최선의 방법을 찾는 방법
ex) TSP (Traveling Salesman Problem)
// 반복문을 통한 1, 2, 3 을 포함하는 모든 순열을 생성하기
for i from 1 to 3
for j from 1 to 3
if j != i then
for k from 1 to 3
if k != i and k != j then
print i, j, k
end if
end for
end if
end for
end for
//재귀 호출을 통한 순열 생성
numbers[] : 순열 저장 배열
isSelected[] : 인덱스에 해당하는 숫자가 사용 중인지 저장하는 배열
perm(cnt) // 현재까지 뽑은 순열 수의 개수
if cnt == 3
순열 생성 완료
else
for i from 1 to 3
if isSelected[i] == true then contiue
numbers[cnt] <- i
isSelected[i] <- true
perm(cnt + 1)
isSelected[i] <- false
end for
// 비트마스킹을 통한 순열 생성
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()
Java
복사
완전탐색 - 조합(Combination)
- 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것
- nCr = n! / ( (n-r)! * r! )
// 반복문을 통한 조합 생성 (1,2,3,4 중 3개)
for i from 1 to 4
for j from i+1 to 4
for k from j+1 to 4
print i, j, k
end for
end for
end for
// 재귀 호출을 이용한 조합 생성 알고리즘
input[] : n개의 원소를 가지고 있는 배열
numbers[] : r개의 크기의 배열, 조합이 저장될 배열
comb(cnt, start) // cnt : 현재까지 뽑은 조합 원소 개수, start :조합을 시도할 원소의 시작idx
if cnt == r
조합 생성 완료
else
for i from start to n-1
numbers[cnt] <- input[i];
comb(cnt + 1, i + 1);
end for
end comb()
Java
복사
완전탐색 - 부분 집합
- 원소들의 그룹에서 최적의 부분 집합을 찾아내는 문제 ex) knapsack 문제
부분집합의 수
- 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 개수는 2^n 개이다.
- 이는 각 원소를 부분집합에 포함시키거나, 포함시키지 않는 2가지 경우를
모든 원소에 적용한 경우의 수와 같다.
부분집합에 속하는 문제들 ex
- 유한 개의 정수로 이루어진 집합 중 특정 원소를 모두 더한 값이 N이 되는 경우를 찾기
⇒ 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야함
// 반복문을 통한 1, 2, 3 집합의 모든 부분집합(Power Set) 생성
for i in 1 -> 0
selected[1] <- i
for j in 1 -> 0
selected[2] <- i
for j in 1 -> 0
selected[3] <- k
for m in 1 -> 3
if selected[i] == 1 then
print i
// 재귀를 통한 부분집합 생성
input[] : 숫자 배열
isSelected[] : 부분집합에 포함/비포함 여부를 저장한 배열
generateSubSet(cnt) // cnt : 현재까지 처리한 원소 개수
if(cnt == N)
부분집합 완성
else
isSelected[cnt] <- true
generateSubSet(cnt + 1)
isSelected[cnt] <- false
generateSubSet(cnt + 1)
end generateSubset()
// 바이너리 카운팅을 통한 부분집합 생성
public class BinaryCounting {
static int N = 3,R = 3;
public static void main(String[] args) {
int[] arr = {1,3,5,7,9};
int size = 1 << arr.length;
for(int i = 1; i < size; i++) { // 2^5 의 모든 경우의 수에 대해
for(int j = 0; j < arr.length; j++) {
if((i & 1 << j) != 0) System.out.print(arr[j] + " ");
}
System.out.println();
}
}
}
Java
복사
순열 & 조합 - next_permutation
next_permutation
- 현 순열에서 사전 순으로 다음 순열을 생성한다.
알고리즘
- 배열을 오름차순으로 정렬한 후 시작한다. (모든 순열의 경우를 찾기 위해)
- 아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성
1. 뒤쪽부터 탐색하며 교환위치 ( i - 1 ) 찾기 ( i : 꼭대기 )
2. 뒤쪽부터 탐색하며 교환위치 ( i - 1 ) 와 교환할 큰 값 위치 ( j ) 찾기
3. 두 위치 값 ( i - 1 , j ) 교환
4. 꼭대기 위치 ( i )부터 맨 뒤까지 오름차순 정렬
// next_permutation 사용법
do{
//완성된 순열 사용
}while(next_permutaion(arr));
// next_permutataion & swap 구현
static boolean next_permutation(int[] arr) {
int N = arr.length;
// step1. 뒤쪽부터 탐색하며 교환위치 찾기 (내림차 아닐 때)
int i = N-1;
while(i > 0 && arr[i-1] >= arr[i]) --i;
if(i == 0) return false; // 만약 교환할 게 없다면 return ;
// step2. 뒤쪽부터 탐색하며 i - 1과 교환할 j 찾기
int j = N-1;
while(arr[i-1] >= arr[j]) --j;
// step3. i - 1, j 교환
swap(arr, i-1,j);
// step4. 꼭대기 위치부터 맨 뒤까지 오름차순 정렬
int k = N-1;
while(i < k) swap(arr, i++, k--);
return true;
}
static void swap(int[] arr, int fst, int snd) {
int temp = arr[fst];
arr[fst] = arr[snd];
arr[snd] = temp;
}
Java
복사
