[코딩 테스트 준비 - 기초] 5. 브루트 포스 - 재귀 & 백트래킹

1. 재귀함수 작성 방법

이전 글에 더해 재귀함수 작성법을 자세히 설명한다.

• 재귀함수는 i 번째 방법과 i+1 번째 방법의 패턴이 동일한 경우 사용한다.
• 재귀함수를 작성할 때는 기준을 정해야 한다. 어떤 기준에 따라서 함수를 호출할지 정하는 것이다.
• 다음으로 넘어갈 때 변화하는 것에 집중해 이를 함수의 인자로 만들거나 따로 관리해야 한다.

 

재귀함수의 기준과 인자를 결정한 다음에는,

1. 다음으로 넘어갈 때 함수를 어떻게(각각의 경우에 값이 어떻게 변화하는지, 변화에 따라 어떻게 호출할 것인지) 호출할 것인지 파악한다.
2. 정답을 찾은 경우를 파악한다 = 재귀 종료 조건
3. 불가능한 경우를 파악한다 (문제의 조건이 지켜지지 않은 경우 or 답을 찾을 수 없는 경우)

 

구현 Point

1. 재귀함수 호출 전, 그 함수를 호출하기 위한 상태를 미리 준비해둬야 한다.
2. 재귀함수 호출이 끝난 것은 해당 경우가 끝난 것으로, 원 상태로 돌려줄 필요가 있다.
3. 재귀의 종료 조건을 설정하는 것이 중요하다.

 

📌 백준 참고 문제

• https://www.acmicpc.net/problem/9095
• https://www.acmicpc.net/problem/1759
• https://www.acmicpc.net/problem/14501

 

2. 백트래킹

백트래킹은 모든 경우를 다 해보는 브루트포스에서 조건을 추가(bouning function)해 의미없는 반복을 하지 않도록 하는 것이다. 즉, 재귀함수에서 더 이상의 호출이 의미없는 경우 이를 중단시키는 것이다. 

 

브루트포스, 재귀, 백트래킹 이름만 다를 뿐 구현하는 데 있어서는 비슷하다. 핵심은 반복을 줄이는 방법을 찾아 적용한는 것!

 

[백준 14889 스타트와 링크]

-> 구현에서 계속 막힌다 이해가 잘 안 된다.. 다음에 다시 시도하자

 

[백준 2529 부등호]

• 기준을 위치(idx)로 잡고, 지금까지 만들어진 수를 num인자로 사용한다.
• 함수 호출 전 현재 위치에 들어가는 값과 이전에 들어간 값이 부등호를 넣었을 때 성립하는지 미리 확인한다. (ok 함수를 통해)
• 이렇게 조건을 걸어 만족하지 않는 경우 재귀함수를 호출하지 않도록 하는 것을 백트래킹이라고 한다.

#include <iostream>
#include <vector>
using namespace std;

int k;
vector<char> ops;
bool visited[10];
vector<string> ans;

bool ok(char x, char y, char op){
    if(op == '<'){
    	if(x > y) return false;
    } else{ //'>'
    	if(x < y) return false;
    }
    return true;
}

void go(int idx, string num){ //idx: 위치, num: 지금까지 만들어진 수
	if(idx == k+1){
		ans.push_back(num);
		return;
	}
	for(int i=0; i<10; i++){
		if(!visited[i]){
			if(idx == 0 || ok(num[idx-1], i+'0', ops[idx-1])){
				visited[i] = true;
				go(idx + 1, num + to_string(i));
				visited[i] = false;
			}
		}
	}
}

int main(){
	cin>>k;
	for(int i=0; i<k; i++){
		char c;
		cin>>c;
		ops.push_back(c);
	}
	go(0, "");
	cout<<ans[ans.size()-1]<<'\n';
	cout<<ans[0]<<'\n';
	return 0;
}

 

브루트포스로 풀었을 때와 백트래킹으로 풀었을 때 시간차이는 다음과 같다.

위) 백트래킹. 아래) 브루트포스

 

 

cf) minmax_element

• c++의 <algorithm>헤더에 벡터의 min과 max를 구하는 메서드가 있다!
• 답을 출력하는 부분을 아래와 같이 써도 된다.

#include <algorithm>

auto p = minmax_element(ans.begin(), ans.end());
cout<<*p.second<<'\n'; //max
cout<<*p.first<<'\n'; //min

 

cf) int to char

• int 값에 '0'을 더하거나 48을 더하면 된다. (ASCII 코드에서 '0'이 48이기 때문)

int i = 0;
cout<<i + '0'<<'\n; //char