Brute Force(완전 탐색)

 

📍 brute force

- 사전적 의미: brute(무식한) + force(힘)

즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 

 

전체를 탐색한다는 의미에서 완전 탐색이라고도 한다.

 

💥 brute force의 장점 

- 알고리즘을 설계하고 구현하기 매우 쉽다.

- 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 

 

💥 brute force의 단점

- 알고리즘의 실행 시간이 매우 오래 걸린다.

- 메모리 효율이 매우 비효율적이다.

 

💥 brute force의 종류

선형구조와 비선형 구조로 나눌 수 있다.

- 선형 구조: 순차 탐색

- 비선형 구조: 백트래킹, DFS, BFS

 

💥 brute force 예시

만약 5자리 비밀번호 자물쇠가 있다고 가정해보자.

자물쇠를 풀기 위해 brute force 방법을 적용한다면 00000 ~ 99999까지 모든 수를 대입해서 풀어야한다. 

모든 경우를 무식하게 탐색하는 brute force 방법을 사용한다면 정답을 찾을 수 있겠지만,

짧은 시간안에서의 문제 해결은 어렵고, 메모리적으로도 매우 비효율적이다.