완전 탐색 알고리즘(Brute-Force Algorithm)
📌 완전 탐색 알고리즘
완전 탐색 알고리즘(Brute-Force Algorithm)이란 순전히 컴퓨터의 성능에만 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법을 말한다. 최악의 시나리오를 취하더라도 솔루션을 찾기 위해 사용하는 방법이다.
컴퓨터 과학에서 Brute Force는 시행착오 방법론을 의미한다. 공간복잡도와 시간복잡도의 요소를 고려하지 않고 순전히 컴퓨터의 성능에 의존한다.
암호학에서도 완전 탐색은 많이 사용된다. 흔히 Brute Force Attack이라고 불리며, 특정한 암호를 풀기 위해 모든 값을 대입하는 방법이다. 수많은 시행착오를 통해 민감한 데이터를 해킹한다. 무차별 대입 공격이 다른 해킹 방법과 다른 점은 지능형 전략을 사용하지 않는다는 점이다.
예를 들어 0-9 사이의 4자리 숫자로 된 자물쇠가 있고, 이 자물쇠의 비밀번호를 잊어버렸다고 생각해보자.
자물쇠를 풀기 위해선 비밀번호를 0000부터 9999까지의 경우의 수를 하나하나 대입하여 자물쇠를 열어야 한다. 최악의 경우 10000번의 시도를 수행해야 한다. 이러한 형식의 방법론을 바로 완전 탐색 방법론이라고 볼 수 있다.
✔️ 완전 탐색 알고리즘을 사용해야할 때
다음의 경우 완전 탐색을 사용하는 것을 고려해볼만하다.
- 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
- 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야할 때
완전 탐색은 어떤 문제의 해결 방법을 생각할 때 가장 쉽게 접근해볼 수 있는 방법론이다. 그리고 그만큼 많이 사용되고 있다. 예를들어 반복문에서 반복문의 범위를 줄이지 않고 하나하나 비교한다면 그것 또한 완전 탐색의 방법론이다.
📌 완전 탐색 알고리즘의 활용
✔️ 순차 검색 알고리즘
배열 안의 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색한다.
int n = arr.length; // 현재의 배열 개수를 n에 할당한다.
boolean result = false;
for(int i = 0; i < n; i++) {
if(arr[i] == K) {
result = true;
}
}
return result;
✔️ 문자 매칭 알고리즘
길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지 검색한다.
int n = arr.length;
int m = patternArr.length;
for (int i = 0; i < n - m; i++) {
int j = 0;
while (j < m && patternArr[j] == arr[i + j]) {
j = j + 1;
}
if (j == m) {
return true;
}
}
return false;
✔️ 선택 정렬 알고리즘
전체 배열을 검색해서 현재 요소와 비교하고 현재 요소보다 작다면 값을 교환하면서 오름차순 혹은 내림차순으로 정렬하는 알고리즘이다.
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
✔️ 그 밖의 완전 탐색 알고리즘
- 버블 정렬 알고리즘
- Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search(BFS, DFS)
- 동적 프로그래밍 - DP(Dynamic Programming)
- Closet-Pair Problems by Brute Force
- Convex-Hull Problems by Brute Force