재귀함수를 이용한 완전탐색의 기본에 대해서 (1)

종만북에서 나오지만요. '중복없이 몇 개 중에 몇 개를 선택하는 방법' 너무 중요하게 다루고 있죠.

완전 탐색의 기본 중에 기본 어떤 상황에서 물어봐도 바로 나와야 할 대답입니다.

우선 간단한 for문으로 고르는 방법부터 알아보겠습니다.

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 << endl;
 

이 코드는 1부터 n-1까지 중에서 중복없이 4개를 고르고 있습니다.

실행해보면 바로 뭔지 알수있죠. 하지만 이 for 문의 단점은 10000개 중에 1000개 고르는 문제를 만날때 입니다.

그러면 for 문을 1000개 겹쳐서 써줘야 되잖아요 ㅠ.ㅠ(좌절;;)

하지만, 우리의 구원자 재귀함수가 있잖아요. ㅎㅅㅎ

#include <iostream>
using namespace std;
 
int limit = 10;
int n = 5;
 
void sol(int picked, int cur, vector<int> &v){
    if(picked == limit){
        for(int i = 0; i < v.size(); i++)
            cout << v[i] << ' ';
        cout << endl;
        return;
    }
 
    for(int next = cur + 1; next < n; next++){
        v.push_back(next);
        sol(picked + 1, next, v);
        v.pop_back();
    }
 
    return;
}
 
int main(){
    vector<int> v;
    sol(0, -1, v);
}

이분이 바로 우리의 구원자 입니다. 

시험 단골 문제 삼성, 카카오 어디 할 것 없이 무조건 출제됩니다. 처음에는 이해가 안되도 

아는 사람을 붙잡고 밥을 사주면서라도 무조건 이해하세요!!!!

초보를 위한 설명)

재귀 함수에서 가장 중요한 것은 '탈출 조건'입니다. 

재귀 함수에서 '탈출 조건' (위 코드에서 8번째 줄에 해당)이 없으면 무한 루프를 돌게 됩니다.

99.9% 코드에 탈출 조건이 반드시 있습니다. DP 문제를 풀 때는 이 조건은 'base case' 라고 부릅니다.

하여튼, 중요한 건 return 문이 있다는 것! 

끝.

코드를 분석해 보겠습니다.

8번째 줄에서 내가 limit 개를 다 골랐으면 끝내겠다는 뜻입니다.

for문을 보면 next가 cur + 1로 초기값으로 설정됩니다. 이는 위 코드에서 k = j + 1 이런식으로 초기화

해준 것과 같은 뜻입니다. 여기에서 cur은 이전에 내가 고른 값(위치)가 되겠죠.

이렇게 순서를 강제해주면 중복없이 고를 수 있습니다.

매개변수가 vector<int> &v로 되어 있다는 것도 눈여겨 봐야 합니다.

이렇게 받기 때문에 16, 18번째 줄이 추가된 것입니다.

만약 그냥 복사해서 받았다면 저런 코드를 써줄 필요가 없을 것입니다. 

F5를 눌러 디버깅을 하면서 변수가 어떻게 바뀌는지 보면 이해가 쉽습니다.

마지막 main 함수에서 실행시키는 부분도 매우 중요합니다.

picked는 0으로하고 vector도 저렇게 넣어주는건 대충 알겠는데 cur을 왜 -1로 넣어주어야 하는가.

이 부분도 매우 중요합니다. 만약 cur을 0으로 주면, 시작점이 무조건 0에 고정되어 버립니다. 

그럼 모든 경우의 수를 다 고를 수 없습니다. 

아 그리고 처음 이 코드를 보시는 분들 중에 만약에 10개 중 4개를 고르는데 

8, 9, 10 을 고른 다음에 고를게 없는데 그럼 어떻게 동작하지? 궁금해 할 수도 있습니다.

그 다음 동작을 보면 next 변수가 11로 설정되어 for문은 끝나버리고 return 문을 만나 그냥 끝나버립니다.

필요없는 곳까지 재귀함수가 들어가서 동작기는 하나 알아서 무시하고 끝내버립니다.

효율적이지 않다고 생각해서 더 코드를 까다롭게 짤 수도 있는데 코드에 익숙하지 않다면 하지 않는 것을 

추천드립니다!!

괜히 쓸데없이 최적화하다가 디버깅에 시간이 후루룩 날아가 버리니까요 ㅎㅎㅎ(경험이 너무 많...)

추천 문제)

1. 로또(https://www.acmicpc.net/problem/6603)

2. 암호 만들기(https://www.acmicpc.net/problem/1759) : 처음에 sort 함수로 정렬 후...

3. 일곱 난쟁이(https://www.acmicpc.net/problem/2309)

4. 부분 수열의 합 (https://www.acmicpc.net/problem/1182)