재귀 / 백트래킹

재귀와 백트래킹은 개념은 정말 어려울게 없지만 문제를 풀때는 정말 머리를 쥐어짜내게 만드는거같다...
이 두 개념은 정말 문제를 많이 풀어봐야만 감이 잡히는 개념이기에 관련 문제를 많이 풀어보는걸 추천!

---

재귀 함수

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘이다. 어떠한 문제를 재귀로 푼다는 것은 귀납적인 방식으로 문제를 해결하겠다는 것과 같다. 재귀함수를 작성할 땐, 다음과 같은 조건이 지켜져야 한다.

• 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함.(Base condition)
• 모든 입력은 base condition으로 수렴해야 함.

void func(int n){
    if(n == 0) return;
    cout << n << ' ';
    func(n-1)
}

1부터 n까지의 수를 출력하는 함수를 예시로 들어보자. 함수를 종료시키는 조건인 n==0 부분이 base condition이되며, 자연수 n을 입력받기 때문에 입력값은 자연히 base condition으로 수렴하게 된다. 
위의 두 조건 중 어느하나라도 지켜지지 않는다면 런타임 에러에 빠지게 되니 주의하자.

재귀 함수 특징

• 모든 재귀 함수는 반복문으로도 구현 가능
• 재귀는 반복문에 비해 코드가 간결하지만, 메모리와 시간적인 측면에서는 손해를 본다.
• 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 되서 메모리 제한에 걸릴 수도 있다.
• 자기 자신을 여러 번 호출하게 되면 좀 비효율적일 수 있다.
  아래의 코드의 흐름을 생각해보면 이미 계산이 완료된 n값에 대해서 반복적인 호출이 일어나는 걸 알 수 있다.
  이 때문에 그냥 계산하는거보다 훨씬 더 큰 시간 복잡도를 갖게된다.

int fibo(int n){
    if(n <= 1) return 1;
    return fibo(n-1) + fibo(n-2);
}

---

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘으로, 재귀에 익숙하다면 훨씬 수월하게 접근 가능한 개념이다.

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 (1 ≤ M ≤ N ≤ 8)

백준의15649번을 예시로 가지고 코드에 익숙해져보자. N=4,M=3인 입력이 들어왔을 때의 처리 순서는 다음과 같다.

1. 크기가 3인 비어 있는 리스트를 선언한다
2. 1을 집어넣는다.
3. 중복하지 않는 숫자 중 가장 작은 2를 집어넣는다
4. 동일한 과정을 거쳐 3을 집어넣는다.
5. 리스트가 모두 다 찼으므로 3번 상태로 이동한다.
6. 남아있는 숫자인 4를 집어넣는다.
7. 12로 시작하는 3자리 수의 가능한 모든 출력을 확인하였으므로 2번 상태로 이동한다.
8. 3을 집어넣는다.

해당 과정을 계속 반복해가며 가능한 모든 수를 다 출력하면 되는 것이다. 과정이 이해가 가지 않는다면 바킹독님의 백트래킹 알고리즘 강의를 들어보시길...코드는 다음과 같다.

int n,m;
int arr[10];
bool isused[10]; //만약 1이 사용된거면 isused[1]=true

void func(int k){ 
  if(k == m){ 
    for(int i = 0; i < m; i++)
      cout << arr[i] << ' ';
    cout << '\n';
    return;
  }

  for(int i = 1; i <= n; i++){ 
    if(!isused[i]){
      arr[k] = i; 
      isused[i] = 1; 
      func(k+1); 
      isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
    }
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  func(0);
}

코드를 봐도 솔직히 이해가 잘 안되긴 한다.. 이럴땐 예제 반복 풀이가 답이긴 하지만 우리의 c++은 또 편리한 STL을 제공해준다.
#include <algorithm> next_permutation(시작위치, 끝위치)

int a[3]={1,2,3};
do{
    for(int i=0; i<3; i++){
    	cout << a[i];
    }
    cout << '\n';
}while(next_permutation(a,a+3))

//123
//132
//213
//231
//312
//321

//4개중 2개의 원소를 뽑는 문제, 만약 5개중 3개를 뽑는 문제면 {0,0,0,1,1}
int a[4] = {0,0,1,1};
do{
    for(int i=0; i<4; i++){
    	if(a[i]==0)
        	cout << i+1;
    }
    cout << '\n';
}while(next_permutation(a,a+4));
//0011 -> 12
//0101 -> 13
//0110 -> 14
//1001 -> 23
//1010 -> 24
//1100 -> 34

next_permutation()함수는 주어진 배열의 사전순(오름차순)으로 다음번에 해당하는 수열을 출력해주는 아주 고맙고 편리한 함수이다. 가능한 모든 수열을 출력해주며, 이미 사전상 마지막 순서의 배열이 입력으로 들어오면 false를 출력하고 마무리한다. 
해당 함수를 통해 조합도 구현 가능하다!

 

출처 : https://www.youtube.com/watch?v=Enz2csssTCs&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=13