[알고리즘] 탐색(1) - 완전탐색(Brute-force)

 개념 

완전탐색은 알고리즘에 입문하는 사람들이 가장 처음으로 접하는 내용일것입니다. 그만큼 어려운 내용은 아니며, 말 그대로 완전히 탐색하는 것입니다. 영어로는 brute-force라고 하는데, 이것을 번역해보면 "무식하게 풀기"라는 뜻입니다.

 

 구현 

완전탐색을 할 때 사용되어지는 방식은 크게 두가지로 볼 수 있습니다.

 

1. Iterative
2. recursion

 

1번은 for문을 이용한 풀이 이고 2번은 재귀 호출을 이용하여 푸는 방법입니다.

예를 들어, 1부터 n까지의 합을 구하는 코드를 구성해보겠습니다.

// iterator
// 조건 : n >=1
// 1~n의 합을 반환한다.
int sum(int n)
{
	int ret = 0;
	for (int i = 1; i < n; ++i)
		ret += i;
	return ret;
}

 

이 함수는 n이 1이상일 때 1~n까지의 합을 반환하는 함수입니다. 하지만 이렇게 Iterative하게 구성했을때는 재귀 함수와 비교해서 수정하기나 알아보기가 힘듭니다. 

 

당연히 이 코드는 짧고 간단하기 때문에 쉽게 파악할 수 있지만, 가령 m개의 원소중 n개를 뽑는 조합을 구성한다고 했을때는 n개의 반복문을 구성하고 있어야합니다.

 

for (int i = 0; i < m; ++i)
	for (int j = i + 1; j < m; ++j)
		for (int k = j + 1; k < m; ++k)
			for (int s = k + 1; s < m; ++s)
				for (int r = s + 1; r < m; ++r)
                			.....

 

이 사이사이 조건이 추가된다고한다면 코드를 작성하는 본인조차 실수 할 수 있습니다.

그래서 자주 사용되는 방식이 재귀 호출(recursive function)입니다. 다시 1~n까지의 합을 구하는 함수로 넘어와서 재귀함수를 짜보겠습니다.

 

// 조건 : n >= 1
int recursiveSum(int n)
{
	if (n == 1) return 1;	// base condition (기저 조건)
	return n + recursiveSum(n - 1);
}

재귀 함수에서 중요한 점은 기저 조건입니다. 기저조건이 명확하지 않다면 무한으로 함수를 호출하게되어 stack overflow error가 발생합니다. 재귀 함수의 장점은 기저 조건 혹은 새로운 조건이 추가되더라도 사람이 해석하기 편하게 구성되어있기 때문에 더 깔끔한 풀이가 가능합니다.

 

recursion

 

 시간복잡도 

1~n까지 구하는 코드의 시간 복잡도는 O(n)입니다. 하나의 반복 혹은 n번의 재귀 호출을 하고있기 때문입니다. 하지만 mCr과 같이 반복이 r번 발생하면 복잡도는 O(n^r)으로 굉장히 높습니다. 따라서 기본에 충실하면서 완전탐색을 익히고 최적화 및 다른 알고리즘을 천천히 습득하신다면 더욱 시간복잡도를 낮출 수 있습니다.

 

예를들어 1~n까지의 합은 사실 sum = n(n+1) / 2으로  O(1)의 복잡도로 문제를 해결할 수도 있습니다.

 정리 

위에서 말한 m개의 원소중 n개를 뽑는 mCn을 포함해서, 중복조합, 조합, 중복순열, 순열 등 많은 완전탐색 기법이 존재합니다. 그렇다고 완전탐색으로 모든 문제가 풀리진 않습니다.

 

그래서 이번 탐색 시리즈에서는 기본으로 사용되는 완전탐색 기법과 최적화 시킬 수있는 퇴각검색(backtracking), 가지치기  그리고 조금은 어려울 수 있는 이분탐색에 대해서 알아보도록 하겠습니다.

 

 참조 

구종만. 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (Algorithmic Problem Solving Strategies). 인사이트. 2012