백준 알고리즘 기초 - 브루트 포스 (재귀, 백트래킹)

재귀재귀재귀재귀재

 

재귀에는 어느정도 익숙해진듯 하다.

재귀를 풀었을 때 특유의 쾌감도 있는듯..

하지만 갈 길은 아직 멀다....

정리 시작!

-

이전에 풀었던 문제를 재귀를 사용해서 풀어보자.

* 1, 2, 3 더하기 (low) : 정수 n을 1,2,3의 합으로 나타내는 방법의 수 구하기

9095번: 1, 2, 3 더하기

#include <iostream>
using namespace std;

int ans = 0;

void go(int left, int n) {
	if (left == 0) {
		ans += 1;
		return;
	}

	if (left >= 1) go(left - 1, n);
	if (left >= 2) go(left - 2, n);
	if (left >= 3) go(left - 3, n);

	return;
}

int main() {
	int k;
	cin >> k;

	while (k--) {
		int n;
		cin >> n;
		
		go(n, n);
		cout << ans << '\n';
		ans = 0;
	}

	return 0;
}

 - 직관적으로 풀린다.

 

* 암호 만들기 (mid) : 조건을 만족하는 암호를 출력하면 된다. n과 m 문제처럼 생각하면 수월하게 풀린다.

1759번: 암호 만들기

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

char p[15];

void go(int l, int c, int m, int j, int idx, int selected, string &s) {
	if (selected == l && m >= 1 && j >= 2) {
		cout << s << '\n';
		return;
	}

	if (idx >= c) return;

	s += p[idx];
	if (p[idx] == 'a' || p[idx] == 'e' || p[idx] == 'i' ||
		p[idx] == 'o' || p[idx] == 'u') {
		go(l, c, m + 1, j, idx + 1, selected + 1, s);
	}
	else {
		go(l, c, m, j + 1, idx + 1, selected + 1, s);
	}

	if(s.size()) s.pop_back();
	go(l, c, m, j, idx + 1, selected, s);
}

int main() {

	int l, c;
	cin >> l >> c;

	for (int i = 0; i < c; i++)
		cin >> p[i];

	sort(p, p + c);

	string s;
	go(l, c, 0, 0, 0, 0, s);

	return 0;
}

- selected 된 수를 세는 n과 m 문제의 방법을 활용했다.

- 입력 받은 수를 꼭 정렬하고 재귀를 돌리자. 원치 않은 결과를 얻을 수도 있다... 

- go의 인수 중 m은 모음, j는 자음이다. 길이 조건을 만족해도, 모음과 자음의 조건이 충족되지 않으면 출력되지 않는다. 

- 더 깔끔하게 푼 코드는 백준에서 참조하자.. (코드는 너무 올리면 안 될 것 같다)

 

* 퇴사 (mid) : 퇴사 전까지 최대한 상담으로 많은 수익을 내는 문제다.

14501번: 퇴사

#include <iostream>
#include <algorithm>

using namespace std;

int n, t[16], p[16], ans = 0;

void go(int day, int sum) {
	if (day == n + 1) {
		if (ans < sum) ans = sum;
		return;
	}

	if (day > n + 1) return;

	go(day + t[day], sum + p[day]);
	go(day + 1, sum);
}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> t[i] >> p[i];

	go(1, 0);

	cout << ans << '\n';

	return 0;
}

 - 퇴사일 이전에 모든 상담이 끝나야 한다는 것에 주의해서 차근차근 하다보면 어렵지 않게 구할 수 있다.

 

 

* 백트래킹 : 의미 없는 경우는 제외하고 구하는 방법이다. 더이상 진행하는 게 의미 없는 조건을 찾는 게 관건이다.

문제 풀어보자.

 

* 스타트와 링크 (high) : 슬슬 어려워진다. 두 팀의 능력치 차이가 최소가 되도록 팀을 짜고, 능력치 차이의 최솟값을 구하는 문제다. 좀 많이 헤맸다.

14889번: 스타트와 링크

 - a팀으로 가거나 b팀으로 가거나 둘 중에 하나니까, 2^n 가지의 경우를 생각할 수 있다. 그렇게 하다보면 딱 절반으로 안 나눠지는 경우도 있으므로 예외를 잘 생각해야한다.

 - 재귀는 리턴값을 잘 활용해야 더 어려운 문제도 잘 풀 수 있을 것 같다. 리턴값을 활용하는 풀이법에 익숙해지자.

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

int n, s[20][20];

int go(int idx, vector<int> &a, vector<int> &b) {
	if (idx == n) {
		if (a.size() != n / 2) return -1;
		if (b.size() != n / 2) return -1;
		int t1 = 0, t2 = 0;
		for (int i = 0; i < n / 2; i++) {
			for (int j = 0; j < n / 2; j++) {
				if (i == j) continue;
				t1 += s[a[i]][a[j]];
				t2 += s[b[i]][b[j]];
			}
		}

		int diff = abs(t1 - t2);
		return diff;
	}

	if (a.size() > n / 2) return -1;
	if (b.size() > n / 2) return -1;

	int ans = -1;
	a.push_back(idx);
	int t1 = go(idx + 1, a, b);
	if (ans == -1 || t1 != -1 && ans > t1) {
		ans = t1;
	}
	a.pop_back();
	b.push_back(idx);
	int t2 = go(idx + 1, a, b);
	if (ans == -1 || t2 != -1 && ans > t2) {
		ans = t2;
	}
	b.pop_back();

	return ans;
}

int main()
{
	cin >> n;

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

	vector <int> a, b;

	cout << go(0, a, b) << '\n';

	return 0;
}

  - 딱 절반으로 나눠야 하므로, 한 팀이 절반 이상을 가져가는 것도 예외에 포함된다. 이를 추가해주면 실행 속도를 높일 수 있다. 재귀는 정말 예외를 어떻게 설정하느냐에 따라 실행시간이 천차만별이다. 

 

- 부등호 (high) : 풀릴듯 너무 안 풀렸다. 한번 풀었는데도 재귀로 풀려고 하니 좀 까다롭게 느껴졌다.

2529번: 부등호

 - 부등호가 k개이면 수는 k+1개다. 이를 활용해서 부등호에 따라 수가 잘 놓였는지 확인 해야한다.

 - 이 문제 또한 n과 m 문제를 활용해서 풀었다.

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

vector <string> ans;
char boo[10];
bool check[10];
int n;

bool ok(string num) {
	for (int i = 0; i < n; i++) {
		if (boo[i] == '<') {
			if (num[i] > num[i + 1]) return false;
		}
		else {
			if (num[i] < num[i + 1]) return false;
		}
	}
	return true;
}

void go(int index, string num) {
	if (index == n + 1) {
		if (ok(num)) {
			ans.push_back(num);
		}
		return;
	}
	for (int i = 0; i <= 9; i++) {
		if (check[i]) continue;
		check[i] = true;
		go(index + 1, num + to_string(i));
		check[i] = false;
	}
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> boo[i];

	string num;
	go(0, num);

	string u = "", d = "";
	for (int i = 0; i < ans.size(); i++) {
		if (u == "" || u < ans[i]) u = ans[i];
		if (d == "" || d > ans[i]) d = ans[i];
	}

	cout << u << '\n' << d << '\n';

	return 0;
}

  - ok 함수에서는 입력된 수가 부등호에 따라 잘 배열 되어 있는지 확인한다. 조건에 부합하면 벡터에 저장하고, 이중 최댓값과 최솟값을 구하면 된다.

 - 여기서도 예외를 따로 설정해주면 속도가 굉장히 빨라진다. 다음 재귀로 넘어갈 때, 방금 사용한 부등호가 올바른지 바로 확인하고 틀렸다면 뒤에 부등호를 검사할 필요가 없으므로 바로 넘어가면 된다.

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

vector <string> ans;
char a[10];
bool check[10];
int n;

bool good(char num, char n, char a) {
	if (a == '<') {
		if (num > n) return false;
	}
	else {
		if (num < n) return false;
	}
	return true;
}

void go(int index, string num) {
	if (index == n + 1) {
		ans.push_back(num);
		return;
	}
	for (int i = 0; i <= 9; i++) {
		if (check[i]) continue;
		if (index == 0 || good(num[index - 1], i + '0', a[index - 1])) {
			check[i] = true;
			go(index + 1, num + to_string(i));
			check[i] = false;
		}
	}
}

int main()
{
	cin >> n;

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

	string num;
	go(0, num);

	string u = ans[0], d = ans[0];
	for (int i = 1; i < ans.size(); i++) {
		u = max(u, ans[i]);
		d = min(d, ans[i]);
	}

	cout << u << '\n' << d << '\n';

	return 0;
}

 - 새로운 함수를 설정해서 방금 사용한 부등호가 올바르게 사용됐는지 확인하고, 틀렸다면 그 뒤의 경우는 생각하지 않고 바로 다음으로 넘어가면 된다.

 

* 맞춰봐 (hard) : 열심히 풀어서 답에 근접하긴 했지만 자꾸 시간초과가 떴다. 백트래킹을 사용하지 않으면 못 푸는 문제였다. 예외를 생각하는 연습이 더 필요할 것 같다. (내가 본 백준 문제 중에 가장 서론이 길었다)

1248번: 맞춰봐

 - (-)10부터 10까지를 생각하면 양수, 음수, 0 으로 나눌 수 있다. 여기서 모든 경우를 구하려면 양수는 1~10, 음수는 -10 ~ -1, 0은 0 하나를 생각할 수 있다. 양수와 음수는 굳이 부등호를 붙여가면서 따로 계산하지 말고 각각 1, -1을 저장해 1에서 10까지 반복문을 돌려 각각 곱해주면 된다. 그럼 굳이 char 형으로 배열을 안 잡고 int형으로 계산을 할 수 있다. 이 아이디어는 다른 문제에서도 써먹을 수 있으니까 꼭 기억해두자.

 - 얘도 백트래킹을 사용하지 않으면 시간초과가 뜬다. 불필요한 경우를 제외하고 반복문을 돌도록 예외를 설정해줘야 한다. 각각의 수를 넣어줄 때마다, 조건을 만족하는지 확인하고 그렇지 않다면 그 뒤의 경우는 건너 뛰도록 해준다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n;
int s[10][10], ans[10];

bool check(int idx) {
	int sum = 0;
	for (int i = idx; i >= 0; i--) {
		sum += ans[i];
		if (s[i][idx] == 0) {
			if (sum != 0) return false;
		} 
		else if (s[i][idx] > 0) {
			if (sum <= 0) return false;
		} 
		else if (s[i][idx] < 0) {
			if (sum >= 0) return false;
		}
	}
	return true;
}

bool go(int idx) {
	if (idx == n) {
		return true;
	}

	if (s[idx][idx] == 0) {
		ans[idx] = 0;
		return check(idx) && go(idx + 1);
	}
	
	for (int i = 1; i <= 10; i++) {
		ans[idx] = s[idx][idx] * i;
		if (check(idx) && go(idx + 1)) return true;
	}
	return false;
}

int main()
{
	cin >> n;
	string sign;
	cin >> sign;

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			if (sign[cnt] == '0')
				s[i][j] = 0;
			if (sign[cnt] == '+')
				s[i][j] = 1;
			if (sign[cnt] == '-')
				s[i][j] = -1;
			
			cnt += 1;
		}
	}

	go(0);
	for (int i = 0; i < n; i++)
		cout << ans[i] << ' ';

	return 0;
}

 - 재귀도 많이 풀어보는 게 답인 것 같다. 이제 어느정도는 감이 오는데, 연습이 더 필요할듯 하다.

-

브루트 포스가 끝나간다. 이 챕터가 기초에 잘 어울리는 챕터가 아닌가 하는 생각이 든다.

진짜 말 그대로 다 해보는 거니까.. 근데 이제 머리를 좀 써서 안 해도 될 거는 안 하는 것까지 배웠다.

다음 단원에서 조금 더 업그레이드 해보자.

정리 끝!