브루트 포스
brute : 무식한, force : 힘. 무식한 힘으로 해석할 수 있다.
완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색해 해를 찾는다.
- 브루트 포스의 가장 흔한 문제점은 숫자가 커질수록 시간복잡도가 엄청나게 늘어나는 것이다.
브루트 포스 종류
자료의 구조에 따라서 브루트 포스는 2종류로 나뉘게 되는데,
- 선형구조 : 순차 탐색
- 비선형구조 : BFS, DFS
1. 순차 탐색
순차 탐색을 하는 방식은 정형화 되어있다.
- 문제에서 주어진 자료를 선형 구조로 바꾼다.
- 구조화된 자료들을 구조에 맞는 방법으로 해를 구할 때까지 탐색한다.
- 탐색한 해를 주어진 문제의 출력 형식에 맞게 정리한다.
순차 탐색 예시 : https://velog.io/@hyesoup/%EB%B0%B1%EC%A4%80-2798%EB%B2%88-%EB%B8%94%EB%9E%99%EC%9E%AD
2. BFS
선형 탐색을 이용하여 탐색을 할 수 없는 구조들이 있다. 대표적으로 그래프 자료구조이다. 그래프 형태의 자료구조들은 탐색을 할 때, 선형 탐색이 불가능하기 때문에 비선형 탐색법을 사용해야 한다. 그 중 하나가 BFS이다.
3. DFS
DFS는 이름과 같이 루트에서 가장 끝에 있는 막다른 노드까지 탐색을 해서 재귀적으로 함수가 탐색을 갔다가 빠져나오면서 연결된 노드들을 탐색하는 방식이다.
출처
https://velog.io/@easttwave/Algorithm-Brute-Force%EB%B6%80%EB%A5%B4%ED%8A%B8-%ED%8F%AC%EC%8A%A4
https://hcr3066.tistory.com/26
:]