백준 알고리즘 중급 - 브루트 포스 : 재귀 (연습) - 1

아리까리 재귀

주로 풀었던 문제를 다른 방법으로 푸는 식이었다.

더 빨리 풀리는 문제도 있었고, 오히려 더 느리게 풀리는 문제도 있었다.

어쨌든 재귀를 사용하면 식 자체는 간단해진다. 하지만 까딱 잘못하다가는

메모리가 오버 되거나 무한 루프에 빠지기 쉽다. 제한 조건을 잘 걸어줘야 한다.

정리 시작!

-

* 로또 (mid) : 앞에서 순열을 사용해서 풀었던 문제를 재귀로 풀어봤다.

6603번: 로또

#include <iostream>

using namespace std;

int k, a[13], ans[13];

void go(int a[], int idx, int cnt) {
	if (cnt == 6) {
		for (int i = 0; i < 6; i++)
			cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	if (idx == k) return;

	ans[cnt] = a[idx];
	go(a, idx + 1, cnt + 1);

	ans[cnt] = 0;
	go(a, idx + 1, cnt);
}

int main()
{
	cin >> k;

	while (k) {
		for (int i = 0; i < k; i++)
			cin >> a[i];
		go(a, 0, 0);
		cout << '\n';
		cin >> k;
	}

	return 0;
}

- 재귀 함수에 들어갈 인수를 어떻게 설정해주냐, 언제 리턴을 하냐를 설정하는 것이 관건이다.

- 재귀 안에서 선택 하는 경우와 선택하지 않는 경우로 나눠 차례대로 계산해줄 수 있다.

 

* 부분 수열의 합 (mid) : 로또 문제와 큰 차이가 없다.

1182번: 부분수열의 합

#include <iostream>

using namespace std;

int n, s, a[20], ans = 0;

void go(int a[], int idx, int sum) {
	if (idx == n) {
		if (sum == s) {
			ans += 1;
		}
		return;
	}

	go(a, idx + 1, sum + a[idx]);
	go(a, idx + 1, sum);
}

int main()
{
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> a[i];

	go(a, 0, 0);
	if (s == 0) ans -= 1;

	cout << ans << '\n';

	return 0;
}

- 로또 문제는 '선택하느냐, 안 하느냐'에서 끝났다면, 이 문제는 '선택해서 더할 거냐, 안 더할 거냐'다.

- 하나 신경 써야할 부분은 합이 0인 수를 구할 때는 1을 빼줘야 한다는 것이다. 양수 개수의 부분 수열의 합을 구한다는 조건이 있으므로, 아무 것도 선택하지 않고 0을 구하는 경우를 하나 빼줘야 한다.

 

* 부분수열의 합 (mid) : 아까 문제는 어떤 수를 제시하고 그 수를 만들 수 있는 조합의 개수를 구했다면, 이번 문제는 부분 수열의 합으로 만들 수 없는 가장 작은 자연수를 구하는 문제다. 앞의 문제를 조금만 손 봐주면 된다. 

14225번: 부분수열의 합

#include <iostream>

using namespace std;

int n, a[20];
bool check[2000001];

void go(int a[], int idx, int sum) {
	if (idx == n) {
		if (check[sum] == false) 
			check[sum] = true;
		return;
	}

	go(a, idx + 1, sum + a[idx]);
	go(a, idx + 1, sum);
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];

	go(a, 0, 0);

	int ans;
	for (int i = 1;; i++) {
		if (check[i] == false) {
			ans = i;
			break;
		}
	}

	cout << ans << '\n';

	return 0;
}

- 범위가 얼마 안 되니까, 그만큼의 공간을 만들어서 표현 가능 여부를 체크해준다. 그 후 앞에서부터 쭉 검사하면 된다.

 

* 연산자 끼워 넣기 (mid) : 우선순위에 관계 없이 앞에서부터 계산해준다. 기존에 순열로 풀었던 방식보다는 꽤 신경 쓸 부분이 많았다.

14888번: 연산자 끼워넣기

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

int n, a[11];
int ans_min = 1000000000, ans_max = -1000000000;

pair<int, int> go(int a[], int idx, int ans, int p, int mi, int mul, int div) {
	if (idx == n)
	{
		return make_pair(ans, ans);
	}

	vector<pair<int, int>> v;
	if (p > 0) v.push_back(go(a, idx + 1, ans + a[idx], p - 1, mi, mul, div));
	if (mi > 0) v.push_back(go(a, idx + 1, ans - a[idx], p, mi - 1, mul, div));
	if (mul > 0) v.push_back(go(a, idx + 1, ans * a[idx], p, mi, mul-1, div));
	if (div > 0) v.push_back(go(a, idx + 1, ans / a[idx], p, mi, mul, div-1));

	auto val = v[0];
	for (auto p : v) {
		if (val.first < p.first) val.first = p.first;
		if (val.second > p.second) val.second = p.second;
	}
	return val;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	
	int plus, minus, mul, div;
	cin >> plus >> minus >> mul >> div;

	pair<int, int> ans = go(a, 1, a[0], plus, minus, mul, div);

	cout << ans.first << '\n';
	cout << ans.second << '\n';

	return 0;
}

- 종료 조건일 때의 리턴값과, 중간 리턴값을 잘 생각해서 넣어준다. 처음에 종료 조건의 리턴값에서 최대, 최솟값까지 계산을 하려다가 런타임 에러가 났는데 중간에 생성되는 리턴값이 없어서 생긴 문제였다.

- auto 함수가 여러모로 유용하다. 아직은 좀 어색한데, 좀 더 익숙해지면 빠르게 코딩하는데 잘 써먹을 수 있을 것 같다.

 

* 연산자 끼워넣기 (2) (mid) : 연산자가 수 - 1개보다 많은 경우를 계산하는 문제다.

15658번: 연산자 끼워넣기 (2)

- 이것저것 만져서 답을 구하긴 했는데, 알고보니 위의 코드와 답이 똑같았다. 어차피 idx가 n이 되는 조건에 걸리기 때문에 연산자가 여러개 있어도 같은 코드로 구할 수 있다.

 

* 두 동전 (high) : 여기서 많이 헤맸다. 접근은 비슷하게 했지만 결국 답을 구하지는 못 했다.

16197번: 두 동전

- 생각해줘야 할 조건이 많았다. 다음 칸이 범위 안에 있는지, 동전이 몇 개 떨어졌는지, 다음 칸이 빈칸인지 벽인지, 이동 횟수가 10이하인지.. 다 생각은 했는데 요령이 부족했던 것 같다.

#include <iostream>

using namespace std;

int n, m;
char b[20][20];

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int go(int cnt, int x, int y, int u, int v) {
	if (cnt == 11) return -1;

	bool fall1 = false, fall2 = false;
	if (x < 0 || x >= n || y < 0 || y >= m) fall1 = true;
	if (u < 0 || u >= n || v < 0 || v >= m) fall2 = true;

	if (fall1 && fall2) return -1;
	if (fall1 || fall2) return cnt;

	int ans = -1;
	for (int i = 0; i < 4; i++) {
		int x1 = x + dx[i];
		int y1 = y + dy[i];
		int x2 = u + dx[i];
		int y2 = v + dy[i];

		if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && b[x1][y1] == '#') {
			x1 = x; y1 = y;
		}
		if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && b[x2][y2] == '#') {
			x2 = u; y2 = v;
		}

		int temp = go(cnt + 1, x1, y1, x2, y2);
		if (temp == -1) continue;
		if (ans == -1 || ans > temp) {
			ans = temp;
		}
	}
	return ans;
}

int main()
{
	int x = -1, y, u, v;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> b[i][j];
			if (b[i][j] == 'o') {
				if (x == -1) {
					x = i; y = j;
				}
				else {
					u = i; v = j;
				}
			}
		}
	}

	cout << go(0, x, y, u, v) << '\n';

	return 0;
}

- 먼저 두 동전의 위치와 이동횟수를 재귀함수의 인수로 넣는다. 이후 재귀함수에서 이동 횟수가 10회 넘어가는 조건, 동전이 몇 개 올려져 있는지 여부를 체크한다. 동전의 상태를 어떻게 체크하는지 잘 기억해두자.

- 이후 다음으로 이동한 위치가 벽인지 여부를 체크하고, 재귀에 돌입해 최댓값을 구한다. 이리저리 생각할 것이 많았다.

 

* 에너지 모으기 (mid) : 앞의 문제와 비슷한 접근인데, 이런 접근이 나한테 좀 어려운 것 같다. 최종 리턴값과 중간 리턴값을 잘 구분해서 설정해줘야 한다.

16198번: 에너지 모으기

#include <iostream>
#include <vector>

using namespace std;

int go (vector<int> &w) {
	int n = w.size();
	if (n == 2) return 0;
	int ans = 0;
	for (int i = 1; i < n - 1; i++) {
		int energy = w[i - 1] * w[i + 1];
		vector<int> b(w);
		b.erase(b.begin() + i);
		energy += go(b);
		if (ans < energy) ans = energy;
	}
	return ans;
}

int main()
{
	int n;
	cin >> n;
	
	vector<int> w(n);
	for (int i = 0; i < n; i++)
		cin >> w[i];

	cout << go(w) << '\n';

	return 0;
}

 - 이런 식이 뭔가 좀 덜 직관적이라고 해야하나, 암튼 좀 짜고서도 확 와닿지가 않는다. 관련된 문제를 더 많이 풀어서 익숙하게 만들 필요가 있을 것 같다.

 - 재귀 함수 안에 있는 벡터에서 중간값 제거하는 요령은 꼭 기억해두자. 이리저리 많이 쓰일 것 같다.

-

어찌저찌 한 챕터를 또 끝냈다.

한번에 끝내려고 했지만.. 이것저것 할 일이 많아 오늘 알고리즘은 이만해야겠다.

꾸준히 화이팅하자!

정리 끝!