완전탐색

 

재귀적 호출에 대한 개념을 먼저 잡고 넘어가자. 그 이유는 완전 탐색 시에, 해당 호출 방식을 자주 활용하기 때문이다.

 

재귀함수의 기본적인 이해

• 재귀함수란: 함수 내에서 자기 자신을 다시 호출하는 함수
• : 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

• 재귀함수 호출방식

  void RecursiveFunction(void) {     
  	printf("Recursive function example1 \n");     
      RecursiveFunction(); 
  }

※ 기저 사례 (base case)

▷ 더 이상 쪼개지지 않는 가장 작은 작업, 즉 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문에 포함될 내용
▷ 기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 신경써야 한다.

 

---

＃ 완전탐색(exhaustive search)

 

① 완전탐색이란?

▷ '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게

가능한 방법을 전부 만들어 보는 알고리즘

을 뜻한다.
▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.
▷ (예제) n개의 원소 중 m개를 고르는 모든 조합을 출력하는 코드

// n : 전체 원수의 수 
// picked : 지금까지 고른 원소들의 번호 
// toPick : 더 고를 원소의 수
// 일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다. 

void pick(int n, vector<int>& picked, int toPick) {   
	// 기저 사례 : 더 고를 원소가 없을 때 고른 원소들을 출력한다.   
	if(toPick == 0) {
    	printPicked(picked); 
        return; 
    }   
    
    // 고를 수 있는 가장 작은 번호를 계산한다.   
    int smallest = picked.empty() ? 0 : picked.back() + 1;   

    // 이 단계에서 원소 하나를 고른다.   
    for(int next = smallest; next < n; ++next) {
        picked.push_back(next);     
        pick(n, picked, toPick - 1);     
        picked.pop_back();   
    } 
 }

 

② 완전 탐색 방법

• Brute Force for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
• 비트마스크: 거두절미 하고 이야기 하면, 비트마스크는 알고리즘 이라기 보단 테크닉에 가깝습니다. 비트는 컴퓨터에서 다루는 최소 단위이며, 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술을 비트마스크 라고 한다.
• 순열 순열의 시간 복잡도는 O(N!)으로 백트래킹과 비슷하다. check 배열 하나 두고 들어갔다가 나오고, 들어갔다가 나오는 방식을 구현한다. 예시는 밑에 추가해놨으니 참고해보자.
• 백트래킹(DFS): 백트래킹은 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때 만이다. 모든 경우의 수를 모두 찾는 것보다 ‘경우에 따라' 훨씬 빠를 수 있다. 왜냐하면 조건이 만족하는 경우라는 조건이 있기 때문이다.한 컬럼에 Queen을 두었으면 오른쪽 컬럼에 가능한 자리에 Queen을 둔다. 또 다시 오른쪽 컬럼 중에서 가능한 자리에 Queen을 둔다. 이 과정을 반복한다. 만약에 N개의 Queen을 두었다면 카운트를 증가 시킨다. 이제부터가 중요한데, 성공하기 직전으로 상태를 되돌린다(back). 그리고 N번째 컬럼 중 다른 칸들을 시도한다. 만약에 없다면 N-1번째 컬럼에 있는 Queen을 들어서 다음으로 가능한 칸으로 옮긴다. 다시 N번째 컬럼에 Queen을 둘 수 있는 곳을 찾는다. N-1번째 컬럼의 모든 경우를 시도했다면, N-2번째로 되돌아가 다음으로 가능한 위치로 Queen을 옮긴다.
• 구체적인 예를 들어보자. 정렬되어 있지 않은 숫자 리스트 중에 특정 숫자를 찾는 것은 n을 리스트 길이라고 했을 때, O(n) 시간 복잡도를 갖는다. 이 경우에는 백트래킹은 의미가 없다. 한 개씩 모두 살펴볼 수 밖에 없기 때문이다. 반면 N-Queen 문제의 경우는 다르다.

---

#include<iostream> 
#include<vector>   
#define MAX 5 
using namespace std;   

char Arr[MAX]; 
bool Check[MAX]; 
vector<char> V;
void Permutation(int n, int r) 
{     
	if (n == r) {
    	for (int i = 0; i < V.size(); i++) {
        	cout << V[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 0; i < MAX; i++){
    	if (Check[i] == true) continue;
        Check[i] = true;
        V.push_back(Arr[i]); 
        Permutation(n+1 , r);
        V.pop_back();
        Check[i] = false;
    }
}

int main(void) {
	Arr[0] = 'a';
    Arr[1] = 'b';
    Arr[2] = 'c';
    Arr[3] = 'd';
    Arr[4] = 'e';
    Permutation(0,2);
}

#include<iostream> 
#include<vector>   
#define MAX 5 
using namespace std;
char Arr[MAX]; 
bool Check[MAX];
vector<char> V;  
void combination(int idx, int n, int r) {
  if (n == r){
    for (int i = 0; i < MAX; i++){
      if (Check[i] == true){
        cout << Arr[i] << " "; 		        
      } 	    
   	} 	    
  	cout << endl;
  	return;     
  }
  for (int i = idx; i < MAX; i++) {
  	if (Check[i] == true) continue;
    Check[i] = true;          
    combination(i,n+1,r);         
    Check[i] = false;     
  } 
}

int main(void) {
	Arr[0] = 'a';
   	Arr[1] = 'b'; 
    Arr[2] = 'c'; 
    Arr[3] = 'd'; 
    Arr[4] = 'e';
    combination(0,0,2);
}

 

위의 5가지 방법을 이용한 완전탐색 방법 모두를 익히는 것이 좋다.

모든 경우의 수를 탐색하는 방법은 문제를 접했을 때 가장 쉬운 방법이지만, 기초라고도 볼 수 있다. 그리고 문제에서 제한조건과 위의 몇 가지 SKILL을 추가하여 푼다면 문제 해결 시간을 크게 향상 시킬 수 있다. 참고로 완전탐색을 완벽하게 하기 위해서는 DFS, BFS 등등 코드를 두루두루 알고 있어야 한다.