<알고리즘/C++> 완전탐색(Exhaustive Search)

Brute-Force Search라고도 부릅니다 찾아보니 BFS로는 사용하지 않는다고 합니다. 그래서 보통은 Exhaustive Search 아니면 Brute-Force Search 라고 합니다.

BFS는 보통 너비 우선 탐색 알고리즘을 뜻한다고 합니다.

말그대로 완전탐색은 하나씩 하나씩 전부 확인하면서 하는 탐색 기법입니다. 

소스코드를 보면 설명드리겠습니다.

예를들어 0~999까지의 랜덤한 데이터가 존재한다면  이 데이터의 두수의 합이 최대값이 얼마인가를 구한다고 가정을 합니다 당연히 유저는 여기 데이터의 숫자가 몇 인지 알 수 없습니다.

int N, arr[1000];
	cout << "랜덤에서 데이터의 숫자를 얼마를 얻을지 정하시오 1~1000:"<<endl;
	cin >> N;
	srand(NULL);
	
	for (int i = 0; i < N; i++) {
		arr[i] = rand() % 1000;
	}

그러면 MaxResult 를 arr[0](arr[i])와  arr[1](arr[j])부터 arr[999](arr[j])까지 각각 두수의 합을 더해줘서 비교해줍니다.

그리고 다시 arr[1](arr[i]) 와 arr[1](arr[j])을 제외한  arr[0](arr[j])부터 arr[999](arr[j])까지 각각의 두수의 합을 더해줘서 비교해줍니다.

계속 반복해서 ... 

이걸 arr[999](arr[i])와 arr[0](arr[j])부터 arr[998](arr[j])까지 각각 두수의 합을 더해줘서 비교해줍니다.

for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if(i!=j){
				if (MaxResult < arr[i] + arr[j]) {
					MaxResult = arr[i] + arr[j];
				}
			}
		}
	}

결과는 

cout << "최대값" << MaxResult << endl;

999+998 이라는 결과인 1997이라는 값이 나와야 합니다. 당연히 순서대로 하기 때문에 시간의 복잡도는 O(N^2)일겁니다.