무식하게 풀기 (완전 탐색)

 

무식하게 풀기 (완전 탐색)

 

완전 탐색?

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

 

 

재귀 호출과 완전 탐색

 문제를 들여다볼수록 각 조각들의 형태가 유사해지는 작업. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수(recursive function), 혹은 재귀 호출(recursion)이라고 한다.

 

 

재귀 함수

 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다.

 

 

 

반복문 -> 재귀 바꿔보기

 1부터 n까지의 합을 반환하는 for문과 재귀 함수 (알고리즘 문제해결전략1 p147)

int sum(int n) {
    int ret = 0;
    for (int i = 1; i < n; ++i) {
        ret += 1;
        return ret;
    }
}
 
int recursiveSum(int n) {
    if (n == 1) return 1;
    return n + recursiveSum(n - 1);
}

10번째 줄의 if문은 n=1이면 더이상 쪼개지지 않는 최소한의 작업에 도달한 것이다.

이런 것을 가리켜 기저사례(base case)라고 한다.

 

 

 

예제: 중첩 반복문 대체하기

 for문과 재귀를 비교해보자.

(알고리즘 문제해결전략1 p148~149)

 

for문으로 n개 중에 4개 뽑기

for (int i = 0; i < n; ++i) {
   for (int j = i + 1; j < n; ++j) {
       for (int k = j + 1; k < n; ++k) {
           for (int l = k + 1; l < n; ++l) {
               cout << i << " " << j << " " << k << " " << l << "\n";
           }
       }
   }
}

만약 여기서 5개를 뽑는다면 for문이 하나 더 늘어나고, 6개를 뽑는다면 또 늘어나고.... 계속 늘어난다.

 

재귀로 n개 중에 m개 고르는 모든 조합을 찾기

// 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();
    }
}

 

 

 

 

완전 탐색 접근법

1. 최대 크기를 가정하고 제한시간 계산

 => 제한시간 넘어가면 다른 방법 적용

 => 입력의 크기가 작으면 완전탐색을 생각해볼만 함★★★

 

2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나누기

 각 선택은 답의 후보를 만드는 과정의 한 조각이 됨

 

3. 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성

 

4. 조각이 하나 남았을때, 또는 남지 않았을 때 답을 생성했으므로 이것을 기저 사례(종료조건)로 선택해 처리