완전 탐색 알고리즘이란?

완전 탐색은 쉽게 말해 모든 경우의 수를 다 체크해서 정답을 찾는 방법입니다.

이 방법은 무식하게 정답을 찾는다고 해서 Brute Force라고도 부릅니다.

완전 탐색을 이용한 문제 해결은 정답을 얻어낼 수 있는 가장 확실하고 기본적인 방법입니다.

예를 들어, 4자릿수로 되어 있는 자물쇠를 푸는 가장 직관적인 방법은 0000부터 9999까지 모든 경우의 수룰 대입해보는 것입니다.

하지만 문제를 해결하기 위해서는 시간 복잡도나 공간 복잡도 등 고려해야 할 것이 많습니다.

• 문제를 해결할 수 있는가?
• 효율적으로 잘 동작하는가?

물론 완전 탐색을 통해서 문제를 해결하는 것은 가능하겠지만 완전 탐색도 그렇고 대부분의 알고리즘이 2번에서 막히게 됩니다.

예를 들어 백준 1912번 문제를 보자. 참고

완전 탐색으로 이 문제를 풀게 되면 O(N^2)으로 N이 최대 100,000으로 시간 초과가 발생하게 된다. 하지만 DP로 문제를 풀게되면 O(N)으로 문제를 풀 수 있게 된다.

따라서, 완전 탐색을 적용하고자 할 대는 그 문제에 대한 파악이 중요하다.

완전 탐색 기법 활용하기

완전 탐색을 고려할 때는 다음과 같이 수행한다.

• 1. 문제 해결에 필요한 대략적인 모든 경우의 수를 계산한다.
     ( 여기서 시간 복잡도를 고려하여 Go or Stop을 결정한다. 물론 문제를 완전 탐색으로 먼저 풀어보는 방법은 시간이 많은 경우 좋다. 이를 통해 부분 문제가 겹치는지 파악할 수 있거나->그럼 DP나 분할정복으로 생각해보고, 자료구조를 개선해보면서-> 그리디나 효율적인 다른 알고리즘을 생각해볼 수 있음 )
• 2. 이 모든 경우의 수를 구할 수 있는 적절한 방법을 찾아 본다.

여기서 2의 모든 방법에는 다음과 같은 방법이 존재한다. 각 방법에 대해서는 따로 포스팅하겠습니다.

① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법