[C++] ICPC 25W 6회차 - 재귀 및 DnC(분할정복)

1. 재귀함수

함수 안에서 함수 호출 가능. 자기 자신도 호출 가능 >> 재귀함수

void f(int x){ // x=3
	cout << x << ' ';
    f(x-1);
    } //???

• 위는 재귀함수의 예시. 실행과정을 따라가보면 이상한 점 발견 ! x= 3에서 시작한다고 가정
  • 재귀적으로 f(3)이 호출된 후 f(2)가 호출된 후 f(1)이 호출된 후,,, 함수가 종료되지 않음!
• 따라서 재귀함수는 종료조건 또는 기저조건을 설정하는 것이 중요

void f(int x){ // x=3
	cout << x << ' ';
    if(x<=0) return;
    f(x-1);
    } //3 2 1 0

• x<=0일 때 return 으로 함수에서 빠져나간다. 

void f(int x){
	if(x<=0) return;
    f(x-1);
    cout << x << ' ';
    } //1 2 3

• 두 예시를 합친 예시와 호출과정을 시각화한 그림. 재귀호출이 몇 번 중첩돼 있는지를 재귀깊이라 부르기도 한다.

void f(int x){
	cout << x << ' ';
    if (x <= 0) return;
    f(x-1);
    cout << x << ' ';
    } //3 2 1 0 1 2 3

 

 

백트래킹

• 재귀적으로 모든 경우의 수를 탐색하는 문제. 일반적으로 모든 경우의 수를 구하거나 이에 대해 어떤 시뮬레이션을 하는 종류의 문제가 많다.
• 대표적으로 특정조건을 만족하는 순열이나 어떤 집합 원소들의 조합을 구하는 문제들이 있다. 
  • 아래는 1 또는 2로만 이루어진 길이 3의 모든 수열을 백트래킹으로 구하는 과정을 시각화한 것 
  • 백트래킹 문제들은 일반적으로 n 제한을 작게 줘서 재귀깊이 제한

 

비슷한 설정의 문제

N과 M이 주어졌을 때, 1부터 N까지 자연수중에서 중복 없이 M개를 고른 수열을 전부 출력한다.

출력하는 순서는 사전 순으로 증가하는 순서여야 한다.

<제약조건>:

1<=M<=N<=8

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
vector<int>P; //P는 실제 출력할 수열을 저장하기 위한 vector.

void nm1(int cnt){ // cnt는 재귀 깊이를 나타냄. nm1은 문제를 해결하기 위한 함수.
	if(cnt==m){
		for(int i=0; i<cnt; i++){
        	for(int i=0; i<cnt; i++){
            	cout << P[i] << " ";
                }
                cout << '\n';
                return;
                }
    for(int i=1; i<=n; i++){
    	if(find(P.begin(), P.end(),i)==P.end()){
        P.push_back(i);
        nm1(cnt+1);
        P.pop_back();
        }
}

int main(){
	cin>>n>>m;
    nm1(0);
  }

• find 함수는 algorithm 헤더에 포함된 함수. 배열 안에 찾는 값이 있다면 해당 값의 첫 등장 위치에 해당하는 iterator 반환. 없다면 .end() 반환
• find 함수를 사용해서 1부터 N까지 P에 이미 있는 값인지 확인
  • 없다면 P의 맨 뒤에 해당 값을 넣어준다. 그 후 nm1(cnt+1)을 재귀적으로 호출 -> 재귀호출에서 빠져나온 후 넣어줬던 값을 다시 빼 준다. (작은 값부터 확인했기 때문에 사전순으로 원소들이 삽입된다는 것을 알 수 있다.
• 매 재귀 호출마다 원소 하나가 삽입되었다가 삭제되기 때문에 cnt가 P의 길이와 동일한 값이라는 것을 알 수 았다. 따라서 cnt와 P가 같다면 P를 출력하고 함수 호출을 그대로 종료.

분할정복

• 재귀의 대표적인 활용.
• 어떤 문제를 해결하기 위해 더 작은 부분문제들로 나누고 부분문제들을 해결한 뒤 합쳐서 전체문제를 해결하는 방법
  1. 주어진 문제를 간단하게 해결할 수 있다면 그대로 해결
  2. 아니라면 부분문제들로 나눠서 이를 각각 해결
  3. 부분문제들의 답을 합해서 전체 문제 해결
• 어떻게 나누는지가 중요

[색종이 만들기]

• 현재 확인하는 정사각형 영역이 한 색으로만 이루어져 있다면 그 색의 종이를 하나 답에 더하고 탐색 종료
  • 이게 이 문제의 해결하기 쉬운 간단한 형태의 문제에 해당
• 아니라면 문제에서 주어진 조건에 따라 종이를 4개의 영역으로 나눈 후 각 영역을 재귀적으로 탐색.

#include <iostream>
using namespace std;

int arr[130][130];

int sum0=0, sum1=0; //전역변수 선언 -> 각각 하얀 색종이와 파란 색종이의 개수 저장
//재귀적인 호출 내에서 여러 번 업데이트 해야 하는 값은 전역변수로 선언하면 활용하기 편하다.

void f(int x1, int x2, int y1, int y2){
	bool flag=true; //flag라는 변수 선언, 현재 정사각형이 하나의 색으로 이루어져 있는지 나타내는데 사용
    for(int i=y1, i<=y2; i++){ // 이중for문을 통해 현재 정사각형을 확인
    	for(int j=x1; j<=x2; j++){
        	if(arr[i][j]!=arr[y1][x1])[
            	flag=false;
                if(flag){
                	if(arr[y1][x1]==0) sum0+=1;
                    else sum1+=1;
                    }
				else{
                	int xmid=(x1+x2)/2;
                    int ymid=(y1+y2)/2;
                    f(x1, xmid, y1, ymid);
                    f(xmid+1, xmid, y1, ymid);
                    f(x1, xmid, ymid+1, y2);
                    f(xmid+1, x2, ymid1, y2);
               		 }
                }
                
    
    int main(){
    	ios::sync_with_stdio(0);
        cin.tie(0);
        
        int N; cin >> N;
        for(int i=1; i<=N; i++){
        	for(int j=1; j<=N; j++){
            	cin >> arr[i][j];
    }
    }
    f(1,N,1,N);
    cout << sum0 << '\n' << sum1;
    }

• f : 현재 확인하는 [x1,x2] * [y1,y2] 정사각형 영역의 문제를 해결하는 함수.
• 정사각형이 하나의 색으로만 이루어져 있다면 해당하는 색의 개수를 1 증가
  • 아니면 더 작은 4개의 정사각형 영역에 대해 재귀적으로 함수 호출
• 끝점들의 중간 위치를 통해 새로 탐색할 정사각형들의 끝점들 쉽게 계산 가능