📁브루트포스 알고리즘
Brute : 무식한
Force : 힘
직역하면 무식한 힘을 갖는 알고리즘이라는 뜻으로 가능한 모든 경우의 수를 모두 탐색하면서 결과를 도출하여 완전 탐색 알고리즘의 한 종류이지만 완전 탐색의 또 다른 이름으로 불리기도 한다.
- 브루트포스 알고리즘은 대부분 반복문과 조건문을 통하여 답을 도출한다.
- 모든 경우의 수를 전부 탐색하기 때문에 100%의 정확성을 보장하지만 높은 시간 복잡도를 갖는다.
1️⃣ 브루트포스 알고리즘의 사용 조건
1. 문제에서 달성하고자 하는 솔루션이 잘 정의되어 있어야 한다.
솔루션이 잘 정의되어 있지 않은 문제라면 브루트포스를 사용한 솔루션이 올바른지를 확인할 수 없다.
2. 문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.
- 문제에서 고려해야할 솔루션의 수가 한정되어 있어야 한다.
- 고려해야할 솔루션의 수가 무한하거나 너무 크면 브루트포스는 완전 탐색을 하기 때문에 비효율적이다.
2️⃣ 브루트포스 알고리즘 예시
1. 선형 구조 : 순차 탐색
반복문을 사용하는 경우
public class BruteForceLoop {
public static void main(String[] args) {
int[] password = {3,4,5};
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
for(int k = 0; k < 10; k++) {
if(password[0] == i && password[1] == j && password[2] == k) {
System.out.println("비밀번호 : " + i + j + k);
break;
}
}
}
}
}
}2. 비선형 구조 : 백트래킹, DFS, BFS
재귀를 사용하는 경우
public class BruteForceRecursion1 {
public static void main(String[] args) {
System.out.println("10! : " + factorial(10));
}
static int factorial(int n) {
if(n == 1) {
return n;
} else {
return n * factorial(n-1);
}
}
}
public class BruteForceRecursion2 {
public static void main(String[] args) {
System.out.println("fibonacci의 10번 째 수 : " + factorial(10));
}
static int fibonacci(int n) {
if(n == 0 || n == 1) {
return n;
} else {
return fibonacci(n-1) * factorial(n-2);
}
}
}3️⃣ 브루트포스 정리
장점
- 알고리즘을 설계하고 구현하기 쉽다.
- 모든 경우의 수를 탐색하기 때문에 100% 정확성을 보장한다.
단점
- 메모리와 시간복잡도면에서 비효율적이다.
- 피보나치 수열과 같은 경우 모든 경우를 탐색하는 브루트포스를 활용하여 해결이 가능하지만 DP를 사용하여 계산할 때 중복된 계산을 피할 수 있으므로 더욱 효율적이다.
- 브루트포스를 사용하는 것은 항상 효율적이지는 못하며, 더 효율적인 방법이 있는지 고민해보고 사용해야 한다.
