브루트포스[2] - 재귀 함수

브루트포스 재귀함수를 사용하는 예제 문제풀이

 

---

 

재귀함수는 아래 4가지를 먼저 생각하고 알고리즘을 작성하는게 좋다.
1. 인자구성
2. 정답을 찾음
3. 불가능한 경우
4. 다음 경우 호출

어떤 재귀함수의 호출이 이전과 영향을 받지 않을 경우 다이나믹으로 바꿀수 있다.
부분수열 : 앞의 정보가 뒤의 정보에 영향을 주므로 다이나믹이 아님
다이나믹 : 앞의 정보를 몰라도 뒤의 정보 풀이가 가능한 경우.

재귀 문제 풀이

 

6603 로또 : www.acmicpc.net/problem/9663

1 . 재귀 인자

dfs(a : 입력으로 주어진 수, index : 선택할지 말지 결정할 인덱스, cnt : 현재까지 포함한 수의 개수

2.  정답을 찾은 경우

cnt ==6

3. 불가능한 경우

index>=a.size

4. 다음경우

//선택

lotto.push_back(a[index]); 
dfs(a, index + 1, cnt + 1);

//미선택
lotto.pop_back(); 
dfs(a, index + 1, cnt); 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

vector<int> lotto;

void dfs(const vector<int> &a, int index, int cnt) {
	if (cnt >= 6) {
		for (auto i : lotto) {
			printf("%d ", i);
		}
		puts("");
		return;
	}
	int len = a.size();
	if (len <= index) return;

	lotto.push_back(a[index]);
	dfs(a, index + 1, cnt + 1);
	lotto.pop_back();
	dfs(a, index + 1, cnt);
}

int main(void) {
	vector<int> a;
	while (1) {
		int n;
		a.clear();
		lotto.clear();
		scanf("%d", &n);
		if (n == 0) return 0;
		for (int i = 0; i < n; ++i) {
			int num;
			scanf("%d", &num);
			a.push_back(num);
		}
		dfs(a, 0, 0);
		puts("");
	}
}

 

1182 부분수열의 합 : www.acmicpc.net/problem/1182

 

1 . 재귀 인자

dfs(i : 선택할지 말지 결정할 인데스, sum : 현재까지 부분수열의 합

2.  정답을 찾은 경우

i == n && sum == s

3. 불가능한 경우

i == n && sum != s

4. 다음경우

//추가

dfs(i + 1, sum + v[i]);

//미추가

dfs(i + 1, sum);

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int n, s, ans = 0;
void dfs(int i, int sum) {
	if (i == n) {
		if (sum == s) ans++;
		return;
	}
	dfs(i + 1, sum + v[i]);
	dfs(i + 1, sum);
}

int main(void) {
	scanf("%d %d", &n, &s);
	for (int i = 0; i < n; ++i) {
		int num;
		scanf("%d", &num);
		v.push_back(num);
	}
	sort(v.begin(), v.end());
	dfs(0, 0);
	if (s == 0) ans--;
	printf("%d", ans);
}

 

14225 부분수열의 합 : www.acmicpc.net/problem/1182

부분수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 문제

부분 수열을 만드는 방법 : 1. 재귀호출 2. 비트마스크

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int n;
vector<int> ansv;

void dfs(int i, int sum) {
	if (i == n) {
		ansv.push_back(sum);
		return;
	}
	dfs(i + 1, sum + v[i]);
	dfs(i + 1, sum);
}

int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		int num;
		scanf("%d", &num);
		v.push_back(num);
	}
	sort(v.begin(), v.end());
	dfs(0, 0);
	sort(ansv.begin(), ansv.end());
	int ans=1;
	for (auto i : ansv) {
		if (i == ans)
			ans++;
		else if (ans > i) continue;
	}
	printf("%d", ans);

}

 

16197 두 동전 : www.acmicpc.net/problem/16197

경우의수 4^10 약 십만이므로 전부다 해볼수 있다.

어떤 정보를 재귀함수로 넘길것 인가!
동전의 위치만 바뀌므로 동전의 위치만 넘긴다.
-> 동전의 위치를 전역변수로 저장할 것인지, 인자로 넘길것인지 생각.
인자로 넘길 경우 : 재귀 앞에서만 동전의 위치를 수정
전역변수로 할 경우 : 재귀 앞과 뒤 모두 동전의 위치를 수정

 

1. 재귀인자

go(cnt, y1, x1, y2, x2)
cnt : 버튼을 누른 횟수
(y1, x1) : 동전1의 위치
(y2, x2) : 동전2의 위치
2. 불가능 한 경우
cnt == 11, 두 동전 모두 떨어진경우
3. 정답을 찾은 경우
두 동전 중에서 하나만 떨어진 경우
4. 다음 경우

↑↓←→
go(cnt+1, ny1, nx1, ny2, nx2)

#include <iostream>
using namespace std;

int h, w;
int dh[4] = { -1, 1, 0, 0 };
int dw[4] = { 0, 0, -1, 1 };
char a[21][21];
int go(int cnt, int y1, int x1, int y2, int x2) {
	int ans = -1, ret = -1;
	if (cnt == 11) return -1;
	int status = 0;
	if (0 <= y1 && y1 < h && 0 <= x1 && x1 < w) status++;
	if (0 <= y2 && y2 < h && 0 <= x2 && x2 < w) status++;
	if (status == 0) return -1;
	if (status == 1) return cnt;

	for (int i = 0; i < 4; ++i) {
		int ny1, nx1, ny2, nx2;
		ny1 = y1 + dh[i];
		nx1 = x1 + dw[i];
		ny2 = y2 + dh[i];
		nx2 = x2 + dw[i];
		if (0 <= ny1 && ny1 < h && 0 <= nx1 && nx1 < w && a[ny1][nx1] == '#') {
			ny1 = y1;
			nx1 = x1;
		}
		if (0 <= ny2 && ny2 < h && 0 <= nx2 && nx2 < w && a[ny2][nx2] == '#') {
			ny2 = y2;
			nx2 = x2;
		}
		ret = go(cnt + 1, ny1, nx1, ny2, nx2);
		if (ret == -1) continue;
		if (ans == -1 || ret < ans) ans = ret;
	}

	return ans;
}
int main(void) {
	cin >> h >> w;
	int y1, x1, y2, x2;
	y1 = x1 = y2 = x2 = -1;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			cin >> a[i][j];
			if (a[i][j] == 'o') {
				if (y1 == -1) {
					y1 = i;
					x1 = j;
				}
				else {
					y2 = i;
					x2 = j;
				}
				a[i][j] = '.';
			}
		}
	}
	cout << go(0, y1, x1, y2, x2);
}