6. 브루트포스(brute-force) part 1

브루트 포스 - 무식하게 풀기

6.2 재귀호출과 완전 탐색

재귀호출

재귀호출시 쪼개지지 않는 가장 작은 작업에서 함수를 return 하여 종료시켜야 한다.
가장 작은 단위를 기저 사례 (base case)라 한다.

1. 중첩 반복문 대체
2. 완전 탐색 구현
   ex) 모든 조합의 경우의 수 찾기

#include <cstdio>
#include <vector>

/*
    모든 조합의 경우를 출력한다.
    재귀호출을 이용한다.
    다중 for문을 대체할 때 유용하다.
*/

using namespace std;
int cnt = 0;

void printVector(vector<int> v){
    for (auto i : v) printf("%d ", i);
    printf("\n");
}

// nCm
void combination(int n, vector<int> & v, int m){
    if (m == 0) {
        printVector(v);
        cnt++;
        return;
    }
    int smallest = v.empty() ? 0 : v.back() + 1;
    for (int next = smallest; next < n; ++next){
        v.push_back(next);
        combination(n, v, m-1);
        v.pop_back();
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> v;
    combination(n, v, m);
    printf("answer: %d\n", cnt);
    return 0;
}

3. 재귀 호출과 부분 문제
   재귀 호출을 공부하면서 짚고 넘어가야 할 개념 중 하나로,
   문제(problem)와 부분 문제(subproblem)의 정의가 있다.
   
   재귀 호출을 정의할 때 '문제'란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다. 예를 들어 {1, 2, 3}을 정렬하는 문제와, {3, 2, 1}을 정렬하는 문제는 다르다.
   
   재귀 호출시 범위를 조금씩 줄여가면서, 부분 문제를 해결하여, base case까지 도달하여 문제를 해결한다.