재귀적 호출에 대한 개념을 먼저 잡고 넘어가자. 그 이유는 완전 탐색 시에, 해당 호출 방식을 자주 활용하기 때문이다.
재귀함수의 기본적인 이해
- 재귀함수란: 함수 내에서 자기 자신을 다시 호출하는 함수
- : 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수
- 재귀함수 호출방식
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 등등 코드를 두루두루 알고 있어야 한다.
