완전 탐색 알고리즘에 대해서

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

완전 탐색

간단한 문제를 복잡하게 푸는 것은 효율적이지 않다. 따라서, 문제를 마주하면 가장 먼저 "무식하게 풀 수 있을까?" 를 고민해야 한다. 

 

무식하게 푼다는 것은 컴퓨터의 연산 능력에 기대어 가능한 경우의 수를 일일이 나열하며 답을 찾는 것이다.

완전 탐색의 절차 (재귀 호출)

주어지는 조건의 최대 크기로 입력했을 때 시간 내에 계산이 되는지 짐작한다. 가능하면 풀어야 할 문제를 유사한 형태의 작업 조각으로 나눈다. 그 중 하나로 답의 일부를 만들고 나머지 답을 재귀 호출을 통해 완성한다.

 

작업 조각이 하나 남거나, 하나도 남지 않은 경우 답을 생성한 것이므로 이를 기저 사례로 선택해 처리한다. (재귀 호출을 언제 멈출지 결정.)

예제: 재귀 합산

어떤 자연수 n 이 주어지면 1 부터 n 까지의 합을 계산한다.

 

n 개의 숫자를 더하는 문제를 각 숫자를 더하는 작업으로 나눈다. (유사한 형태의 작업 조각으로 나누기.) 조각 n 을 떼어 해결하고 1 부터 n-1 까지의 조각을 재귀 호출해 해결한다.

 

n 이 아닌 1 부터 떼어내 해결하면 2 부터 n 까지의 합이 남는데, 이는 1 부터 n 까지 합을 구한다는 원래 문제와 다르기 때문에 자기 자신을 호출해 계산할 수 없다.

 

n 을 계속 떼어내 해결하다 보면 1 하나의 수를 더해야 하는 작업만 남으므로 이를 기저 사례로 선택해 처리한다. (작업 조각이 1 개만 남았으므로 재귀 호출을 멈춘다.)

C++ 코드

// recursiveSum 은 인자로 받은 n 에 대해 1 부터 n 까지의 합을 구한다.
int recursiveSum(int n){
	// 기저 사례
	if(n == 1) return 1;

	// 작업 조각 n 을 떼어내 해결하고 나머지 1 부터 n-1 까지의 합을 재귀 
	// 호출해 해결한다.
	return n + recursiveSum(n-1);
}