완전탐색이란?
- 완전탐색은 Brute-force Search라고 부르며 알고리즘 문제를 해결할 때 기본적으로 처음 접할 수 있는 방법입니다.
- 한 상황을 생각해 봅시다. 1000개까지 담길 수 있는 배열에서 두개의 가장 큰 수를 찾아 두 수의 합을 출력해보는 문제가 있다고 한다면, 이 두 수를 어떻게 찾을 수 있을까요?
- 쉽게 생각해서 우리는 for문을 활용해 각 배열의 원소들을 더해보고 가장 큰 값을 구하는 방법을 생각해 볼 수 있습니다.
- 즉 쉽게 말하면 모든 경우의 수를 다 탐색해보며 찾아보는 방식이고 그렇기 때문에 시간복잡도는 최대로 O(n^2) 의 시간이 소요됩니다.
-
#include <iostream> #include <algorithm> #include <climits> using namespace std; int Number; int ret = INT_MIN; int main() { int array[1000]; cin >> Number; // Array의 크기를 입력받습니다. for(int i=0;i<Number;i++) // Number의 크기만큼 순회하며 Array의 요소를 채워넣습니다. cin >> array[i]; //여기서 array담긴 숫자들 중 가장 큰 값을 가지는 숫자 2개를 더한 값을 호출해야하는 경우를 생각해봅시다. for(int i=0;i<Number;i++) for(int j=0;j<Number;j++) if (i!=j) // Array의 두 index가 다를 때, 즉 같은숫자의 경우는 제외합니다. ret = max(ret, array[i] + array[j]); //return값을 max함수를 통해 더 큰값으로 갱신합니다. cout << ret; return (0); } - 위 코드를 살펴보면 Array의 담겨있는 최대 1000개까지 담길 수 있는 배열에서 2개의 큰 수를 찾아 결과를 반환하는 것을 확인할 수 있습니다.
- 모든 가능한 경우를 다 돌아보기 때문에 Number크기(Array의 크기)의 제곱만큼의 시간이 소요될 수 있습니다.
- 정답을 찾아내는 방법 중 가장 확실한 방법이지만 그만큼 시간이 많이 소요되기 때문에 알고리즘문제의 제한시간 을 확인해서 사용해야 합니다.
- c++기준으로 1억번의 시간복잡도를 가질 경우 제한시간이 1초 소요되는 것으로 생각하여 문제를 해결합시다.
- 완전탐색 알고리즘을 활용한 문제는 다음 게시글에서 확인할 수 있습니다.