#21. 브루트 포스(Brute Force Search)

브루트 포스(Brute Force Search)

• 완전 탐색 알고리즘
• 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

---

구조에 따른 브루트포스 종류

• 선형 구조 : 순차 탐색
• 비선형 구조 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

 

순차 탐색

 

① 구조화 : 문제에서 주어진 자료를 선형 구조로 구조화한다.

② 탐색 : 구조화된 자료들을 구조에 맞는 방법으로 해를 구할때까지 탐색한다.

③ 정리 : 탐색한 해를 주어진 문제의 출력 형식에 맞게 정리한다.

---

장점

• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

 

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 한다.
• 해가 존재하지 않는다면 유한(finite) 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한(infinite) 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

---

References

 

hcr3066.tistory.com/26

알고리즘 기법[전체 탐색] - 브루트 포스(brute force)