https://hongjw1938.tistory.com/78 를 참고하여 작성함.

완전탐색 알고리즘

---

완전탐색 알고리즘은 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법.
"Brute Force"라고 부르며, 직관적으로 이해하기 쉽고 문제의 정확한 결과값을 얻어내는 가장 확실하며 기초적인 방법이다.

예를 들어 4자리 암호로 구성된 자물쇠를 풀려고 시도하는 경우, 정상적인 자물쇠라면 0000부터 9999까지 모두 시도해보는 방법으로 반드시 해결 가능한 확실한 방법이 된다.

CS에서 문제 해결 알고리즘을 사용할 경우, 2가지 규칙을 적용해야 한다.
먼저 사용된 알고리즘이 적절한지 생각해야 하고, 또 효율적으로 동작하는지 생각해 봐야 한다.

위 두 가지 규칙을 대입했을 때, 완전탐색 알고리즘은 전자의 경우, 만족될 수 있는 가장 확실한 방법이나, 후자의 경우에 걸리기 때문에 이 방법이 사용되기에는 한계가 분명하다.

DP와 비교해서 각각의 알고리즘으로 연속합 문제(백준 1912번)를 푼다고 했을 때, DP 알고리즘으로는 약 O(N)으로 해결 가능하지만 완전 탐색 알고리즘으로는 모든 경우의 수를 따져야 하기 때문에 O(N^2)의 시간복잡도를 가지게 된다.

N의 값이 많아질 수록 문제 해결 시간은 기하급수적으로 늘어나게 되어 풀어낼 수 없는 경우가 발생한다. 완전탐색 기법을 사용 시에는 그 문제를 파악해낼 줄 알아야 한다.

완전탐색 알고리즘의 종류

1. Brute Force
2. 비트 마스크
3. 백트래킹
4. 순열
5. 재귀함수
6. DFS/BFS