[Python] 완전 탐색,브루트 포스(Brute Force)

브루트 포스(Brute Force)=완전 탐색

개념

브루트(Brute) : 무식한 + 포스(Force) : 힘
: 발생할 수 있는 모든 경우를 무식하게 탐색
: 가능한 모든경우의 수를 모두 탐색하면서 요구 조건에 충족되는 결과만을 가져온다.
: 예외 없이 100%의 확률로 정답만을 출력한다.

= 알고리즘 설계의 가장 기본적인 접근 방법 => 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법
해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다.

장점

• 알고리즘을 설계하고 구현하기 매우 쉬움.
• 복잡한 알고리즘 없이 빠르게 구현할 수 있음.

단점

• 알고리즘의 실행 시간이 매우 오래 걸림.
• 메모리 효율면에서 매우 비효율적임.

<선형 구조>

• 순차 탐색

<비선형 구조>

• 깊이 우선 탐색(DFS, Depth First Search)
  - 백트래킹과 관련 깊음
• 너비 우선 탐색(BFS, breadth first search)
  - 브루트 포스와 관련 깊음

문제 해결 방법

1. 주어진 문제를 선형 구조로 구조화함.
2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색
3. 구성된 해를 정리한다.