Algorithm - Exhaustive search (완전탐색)

완전탐색(Exhaustive search)이란?

컴퓨터의 계산능력을 이용하여 경우의 수를 모두 나열하면서 답을 찾는법을 뜻한다

예시로 자물쇠 4자리를 풀때 0000부터 9999까지 10000가지의 수를 모두 무식하게 다

나열하면서 푸는 방식을 뜻한다

 

"무식하게 다 계산하여 푼다"의 의미인 Brute-Force(브루트 포스) 라고 도 부른다

 

완전탐색을 써야할때는

 

경우의 수가 작을때 (입력으로 주어지는 데이터N의 크기가 매우 작을 때 )

문제 조건이 명확하게 모든 경우중 최적값을 찾아라 일때

구현이 쉽고 효율보다는 정확해야할경우

 

완전탐색 그 자체가 알고리즘은 아니고 문제 해결 방법이기때문에

완전 탐색 방법을 이용하기 위해서는 여러가지 알고리즘 기법이 사용됩니다

완전 탐색 기법

단순 Brute-Force

비트마스크(BitMask)

재귀함수

순열

BFS / DFS

 

단순 Brute-Force

아이디어, 최적화를 계산하지않고 가능한 모든 경우의 수를 다 시도해보는

모든 경우의 수를 하나하나 다 검사하여 맞는 답을 찾는것을 뜻한다

보통 for문과 if문으로 모든 case로 구현하여 답을 구한다

 

비트마스크 (Bit Mask)

정수의 이진수 표현을 사용하여 집합 을 0과 1로 표현하여

부분집합을 효율적으로 탐색할 수있게 해주는 방법이다

원소가 { 1, 2, 4, 5 } 가 있다고 해보자

해당 원소로 만들수있는 최대의 가짓수는 2^4 즉 16개이다

 

{1, 2, 4, 5}

Mask(진수)	2진수
0000	{}
0001	{1}
0010	{2}
0011	{1,2}
0101	{1,4}
0110	{2,4}
...	...
1111	{1,2,4,5}

 

나올수있는걸 2진수로 변환해서 나올수있는 가짓수를 다 계산한다 방식이다

이와같이 표현할수있다

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> arr = { 1, 2, 4, 5 };
	//mask를 0 부터 2^arr.size() - 1 까지 돌리기
	// 2^4는 16임 15까지만 돌아야함
	//즉 0 부터 15까지만 돌도록 
	
	//시프트 연산자를 사용하여 왼쪽으로 n비트 이동
	for (int mask = 0; mask < (1 << arr.size()); mask++)
	{
		cout << " { ";
		for (int i = 0; i < arr.size(); i++)
		{
			//mask에서 i번쨰 비트가 켜져있다면
			if (mask & (1 << i))
			{
				cout << arr[i] << " ";
			}
		}
		cout << " } " << endl;
	}
}

 

재귀 함수

문제를 만족하는 경우들을 만들어가는 방식이다

만들고자 하는 부분집합을 A 라고 할때 A = { } 부터 시작해서 원소에 대해서

원소가 조건에 만족이 된다면 A 에 넣고 재귀함수를 돌리고 조건이 만족이 안된다면

A를 그대로 재귀 함수에 넣어주는 방식

 

사용방식

#include <iostream>
#include <vector>
using namespace std;

//arr = 원소들, nowIndex = 현재인덱스, lastIndex = 마지막 인덱스
void permute(vector<int>& arr, int nowIndex, int lastIndex)
{
	//재귀 종료 조건 : 현재 인덱스가 마지막 인덱스면 순열 완성 
	if (nowIndex == lastIndex)
	{
		for (int x : arr)
		{
			//완성된 순열을 출력해라
			cout << x << " ";
		}
		cout << endl;
		return; //재귀 종료
	}

	//현재 인덱스부터 마지막 인덱스까지 반복
	//각 원소를 현재 위치에 놓고 재귀 호출
	for (int i = nowIndex; i <= lastIndex; i++)
	{
		//현재 인덱스와 i번째 원소 교환 , 현재 인덱스에 i번째 원소를 놓기위해 교환
		swap(arr[nowIndex], arr[i]);
		//다음 자리 재귀 호출 , 다음자리를 재귀적으로 채우기
		//주어진 배열의 모든 순열을 생성
		permute(arr, nowIndex + 1, lastIndex);
		//원새 상태로 복원 (backtracking)
		swap(arr[nowIndex], arr[i]);
	}
}
int main()
{
	vector<int> arr = { 1, 2, 5, 4 };
	permute(arr, 0, arr.size() - 1);
}

 

 

 

 

 

----

 

순열

(선택 순서가 결과에 영향을 미치는 경우)

 

C++에서는 next_permutation 라는 함수를 사용하여 재귀함수를 구현할수있다

 

필요한헤더

#include <algorithm>

 

사용방법

 

최소 한번은 실행하고 그 뒤에 조건을 검사해서 반복 여부를 결정하는 do-while문을 사용하면된다

for-while문으로 쓰면 첫 배열 상태는 출력이 안되지만 do-while으로 쓰면

첫배열부터 출력하여 간결하게 사용가능하다

#include <iostream>
#include <vector>
#include <algorithm> // next_permutation
using namespace std;

int main() 
{
	vector<int> arr = { 1, 2, 5, 4 };
	sort(arr.begin(), arr.end());

	do {
		for (int x : arr)
		{
			cout << x << " ";
		}
		cout << endl;
		//next_permutation은 오름차순으로 시작해야만함
	} while (next_permutation(arr.begin(), arr.end()));
}

 

DFS / BFS

 

DFS : Depth First Search (깊이 우선 탐색)

구현방식 : 재귀함수 / 스택

동작방식 : 해당 Branch를 모두 탐색한 이후에 다음 Branch로 이동하는 방식

즉 한경로를 끝까지 탐색한후 다른 경로를 탐색하는 방식

노드 방문시 방문 여부를 검사하지않으면 무한 루프에 빠질수 있음

 

시간복잡도 : 인접리스트로 구현시 O(V+E), 인접 행렬로 구현시 O(V^2)

장점 : 목표노드가 깊을때 값을 빨리 구할수 있다

단점 : 구현시 DFS를 재귀적으로 구현할때 재귀호출이 너무 깊어지면 스택오버플로우가 발생할수있음

재귀 깊이를 너무 깊어지지않도록 해야함

 

 

BFS : Breadth-First Search(너비 우선 탐색)

구현방식 : 큐

동작방식 : 모든 인접노드를 탐색한뒤 그다음 레벨로 이동하는 방식

즉 시작노드를 기준으로 가까운 노드를 먼저 방문

 

장점 : 발견한 경로가 최단 경로

단점 : 경로가 길어지면 많은 메모리 공간을 필요로 한다

 

시간복잡도 : O(V+E)