🗒️ Brute Force(브루트 포스)란?
브루트 포스는 Brute(무식한) + Force(힘) 즉, **발생 가능한 모든 경우를 무식하게 탐색한다는 뜻**을 말한다.
> 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. (수가 커질수록 시간복잡도가 크게 증가)
✏️ 완전탐색의 장단점
장점
- 알고리즘을 설계하고 구현하기 매우 쉽고 용이하다.
- 복잡한 알고리즘 없이 빠르게 구현이 가능하다.
단점
- 알고리즘의 실행 시간이 매우 오래 걸린다.(모든 경우의 수를 탐색하기 때문)
- 메모리 효율 측면에서 매우 비효율적이다.
🏷️ Brute Force(브루트 포스)의 종류
> 선형 구조 - 순차탐색
> 비선형 구조 - 백트래킹, DFS(깊이 우선 탐색), BFS(너비 우선 탐색)
- 순차탐색
순차 탐색은 이름 그대로 앞에서부터 뒤까지 순서대로 탐색하는 방법을 말한다.
ex) 배열, 연결리스트, 스택 등에서 이 방식으로 탐색을 한다.
적은 범위 내에서는 순차탐색을 많이 사용하지만 배열이 커질수록 탐색횟수가 배로 커지기 때문에, 크기가 큰 배열에서는 비효율적일 수 잇다.
대표 문제 : [BOJ - 2798번 블랙잭]
- BFS, DFS
이 두 탐색법의 의미는 각가 너비 우선 탐색과 깊이 우선 탐색이라는 뜻으로 너비 또는 깊이를 중점으로 탐색하냐에 따라 탐색법을 나눌 수 있다.
> 그래프 알고리즘 공부를 하며 더 자세히 정리하도록 하겠습니다. 👻
🦖 글을 마치며
브루트 포스 알고리즘은 모든 경우의 수를 탐색하면 반드시 정답을 찾을 수 있기에 간단한 알고리즘이라고 생각하며 공부했지만 크기가 커짐에 따라 시간 복잡도를 고려해줘야 하는 부분에 있어 문제에 대한 깊은 관찰이 필요하다고 생각합니다.🤐