완전 탐색
- 컴퓨터의 빠른 계산 능력을 활용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방식
- 무식하게 풀어서 Brute-Force
"10개의 정수 원소로 이루어진 수열이 존재한다.
이 수열에서 두 원소를 선택해서 구한 합의 최대값을 구하시오"
위의 질문에 대한 방법은 결국 모든 경우를 다 구한 후 최대값을 구하는 것이다.
10C2=45개의 경우를 모두 구한 후, 최대값을 찾게 된다.
그러나, 위의 예시는 45개이기에 충분히 해결 가능하다.
하지만, 원소의 개수가 10만개 이상이라면? 경우의 수가 어마어마하다.
(물론, 저런 경우, 제한 된 시간에 구하지 못하기에 가장 큰 원소와 두번째 큰 원소를 찾아 더하면 답이 된다.)
그래서 완전 탐색 문제인지를 잘 파악하는게 중요하다
여러 알고리즘 기법
- 단순 브루트 포스
- 비트마스크
- 재귀함수
- 순열
- BFS/DFS
기본적으로 완전 탐색은 N의 크기가 작을 떄 이용 되기에 보통 시간 복잡도가 지수승이나, 팩토리얼 형태로 나올 때 많이 사용된다.
실제 사용하려면?
1. 입력으로 주어지는 N의 크기가 매우 작다.
N=10만, 20만 인 경우도 많다. 하지만 대부분의 경우 완전 탐색 문제는 N의 크기가 매우 작다. 순열, 조합 같은 문제들은 완전 탐색으로 푼다면 기본적으로 시간복잡도가 O(2^N)이나 O(N!)이므로 당연히 N의 크기가 매우 작아야 한다.
2. 답의 범위가 작고, 임의의 답을 선택했을 때 문제 조건을 만족하는 지 역추적이 가능하다.
N의 크기가 작으면 답의 범위 또한 작을 확률이 높다.
Reference
developer