[알고리즘] Brute-force 완전 탐색

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

모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘을 의미한다. 가장 강력하고 확실한 방법이지만 그만큼 시간이 오래 걸리는 탐색기법이다.

구현 방법의 예시 )

4자리 숫자로 된 핸드폰의 암호는 0000, 0001, 0002... 9999 까지 총 1만개(10^4)의 조합 중 하나이므로, 
이를 하나씩 대입해 보면 핸드폰의 암호를 통과할 수 있게 된다.

단점

1. 시간면에서 비효율적인 알고리즘이다.
2. 문제의 복잡도(Complexity)에 매우 민감하다는 치명적인 단점을 가지고 있다. 오버플로우 또는 저장공간의 용량 부족이 일어날 수도 있다.
   이 때문에 문제의 규모가 현재의 자원으로 충분히 커버가 가능한 경우에만 쓰이고, 대부분은 동적 계획법 등으로 많이 우회하는 편이다.

장점

1. 다만 그만큼 만들기도 쉽고, 다른 알고리즘을 생각하는 출발점이 된다. -> BFS/ DFS나 백트래킹..
2. 모든 경우의 수를 탐색하므로 100% 답을 찾는게 가능하다.

연관된 문제: 문제 1 문제 2