완전탐색 (Brute-Force)
완전탐색 알고리즘은 말그대로 모든 경우의 수를 다 조회 하는것이다.
전부 조사하기때문에 강력하지만 시간은 오래걸린다는 단점이 있다.
종류
완전탐색을 푸는 방법은 5가지가 있는데 5가지를 전부 알아두는것이 좋다.
- for문
- 순열 과 조합
- 백트래킹
- BFS
- 비트마스크
for문으로 풀기
합이 10인 순서쌍을 구하는 문제
public class For {
public static int solution() {
int count = 0;
for (int i = 0; i <= 10; i++) {
for (int j = 0; j <= 10; j++) {
if (i + j == 10) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
System.err.println(solution()); // 11
}
}
순열과 조합
3개중 2개 중복되지 않게 뽑기 (조합)
public class Combination {
public static void main(String[] args) {
int n = 3;
int r = 2;
int[] resultArr = new int[r];
combination(resultArr, 0, n, r, 0);
}
public static void combination(int[] arr, int index, int n, int r, int target) {
if (r == 0) {
print(arr, index);
} else if (target == n) {
return;
} else {
arr[index] = target;
combination(arr, index + 1, n, r - 1, target + 1);
combination(arr, index, n, r, target + 1);
}
}
public static void print(int[] arr, int length) {
for (int i = 0; i < length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("");
}
}
/*
0 1
0 2
1 2
*/
3개중 2개를 순서에 맞게 뽑기(순열)
public class Permutation {
public static void main(String[] args) {
int[] arr = {1, 2, 3};
permutation(arr, 0, arr.length, 2);
}
public static void permutation(int[] arr, int depth, int n, int r) {
if (depth == r) {
print(arr, r);
return;
}
for (int i = depth; i < n; i++) {
swap(arr, i, depth);
permutation(arr, depth + 1, n, r);
swap(arr, i, depth);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void print(int[] arr, int r) {
for (int i = 0; i < r; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
/*
1 2
1 3
2 1
2 3
3 2
3 1
*/
참고
- (https://gorakgarak.tistory.com/523) 참고
- (https://gorakgarak.tistory.com/522) 참고