브루트포스 (brute force) 란?
- 완전탐색 알고리즘
- 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만 가져옴
- 브루트포스 알고리즘을 설계할 때는 '해가 하나 이상 존재한다'는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다.
- 전체를 탐색하기 위해 탐색 알고리즘을 사용한다. 순차탐색, dfs, bfs를 도구로 이용
장단점
- 장점
- 알고리즘을 설계하고 구현하기 쉽고, 100%의 정답률을 가진다.
- 단점
- 알고리즘의 실행 시간이 오래 걸린다.
구조에 따른 브루트포스 종류
- 선형 구조 : 순차 탐색
- 비선형 구조 : BFS(너비 우선 탐색), DFS(깊이 우선 탐색)
순차 탐색 방법
- 문제에서 주어진 자료를 선형 구조로 구조화한다. (구조화)
- 구조화된 자료들을 구조에 맞는 방법으로 해를 구할 때까지 탐색한다. (탐색)
- 탐색한 해를 주어진 문제의 출력 형식에 맞게 정리한다. (정리)
BFS
- 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드부터 방문하는 방법
DFS
- 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 (자식들을 우선적으로 탐색하는 방법)
BFS & DFS 는 나중에 자세히 정리할 예정이다! 참조블로그
💻🐯