백준 알고리즘 중급 - 그리디 알고리즘 (연습)

갖고와보니 사진이 좀 무섭다

뭐랄까.. 문제 자체는 그렇게 복잡하지 않았는데..

지나치게 많은 시간이 소요된다.

어찌된 노릇일까. 속도를 좀 더 빠르게 할 수는 없을까..?

ㅠㅠ뭐 실력이 쌓이면 속도도 자연스럽게 빨라지겠지..

의식적으로도 시간을 단축하기 위해 슬슬 노력하자.

정리 시작!

-

* 잃어버린 괄호 (mid) : 식에 괄호를 적절하게 쳐서 최소값을 구하는 문제다.

1541번: 잃어버린 괄호

- 마이너스가 나오는 순간부터 그 뒤는 모두 마이너스가 된다는 것만 알면 바로 풀 수 있다. 근데 그게 생각 안 나면 답이 없다! 그리디가 이래서 골때린다. 가장 중요한 사실을 인지하지 못 하면, 말도 못 하게 귀찮아진다. 어찌저찌 풀 수야 있겠지만, 문제를 관통하는 가장 중요한 개념이 뭔지를 파악하려는 노력을 계속 해야 한다.

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

int main()
{
	string a;
	cin >> a;
	vector<int> num;
	vector<char> op;
	
	int idx = 0;
	for (int i = 0; i < a.size(); i++) {
		if (a[i] == '+' || a[i] == '-') {
			num.push_back(stoi(a.substr(idx, i - idx)));
			op.push_back(a[i]);
			idx = i + 1;
		}
	}
	num.push_back(stoi(a.substr(idx, a.size() - idx)));
	op.push_back('0');

	int ans = num[0];
	bool minus = false;
	if (op[0] == '-') minus = true;
	for (int i = 1; i < num.size(); i++) {
		if (minus) ans -= num[i];
		else ans += num[i];
		if (op[i] == '-') minus = true;
	}
	cout << ans << '\n';
	return 0;
}

- string으로 입력 받은 식을 숫자와 연산자로 나눠 저장하는 것도 꽤나 까다롭다. 하지만 그건 구글링 하면 금방 찾을 수 있는 거고.. 항상 문제의 핵심을 파악하는 것이 우선이 돼야 한다.

- 맨 처음 숫자는 그냥 더해주고, 마이너스 연산자가 등장하기 전까지는 다 더해주다가 등장 이후의 숫자는 모두 빼주면 된다.

 

 * 수 묶기 (mid) : 수를 적절히 묶어서 곱해준 뒤, 합의 최댓값을 구하는 문제다.

1744번: 수 묶기

- 최댓값을 구해야 하기에, 큰 양수끼리, 작은 음수끼리 곱해주면 된다. 다른 정렬을 해야하니 양수 / 음수와 0 저장을 따로 해주는 게 좋겠다.

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

int cal(vector<int> a) {
	const int MAX = 10001;
	int n = a.size();
	int temp = MAX;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (temp == MAX) {
			temp = a[i];
		}
		else {
			if (temp + a[i] < temp * a[i]) {
				ans += temp*a[i];
			}
			else {
				ans += (temp + a[i]);
			}
			temp = MAX;
		}
	}
	if (temp != MAX) ans += temp;

	return ans;
}

int main()
{
	int n;
	cin >> n;
	vector<int> p, m;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		ans += t;
		if (t > 0) p.push_back(t);
		else m.push_back(t);
	}

	int ans2 = 0;
	sort(m.begin(), m.end());
	ans2 += cal(m);

	sort(p.begin(), p.end());
	reverse(p.begin(), p.end());
	ans2 += cal(p);

	cout << max(ans, ans2) << '\n';
	return 0;
}

- 양수는 내림차순으로, 음수와 0은 오름차순으로 정렬한다. 큰 수부터 차례로 짝지었을 때, 두 수의 곱이 합보다 크면 곱해주고, 아니면 그냥 더해준다.

- 그냥 다 더하는 값이 제일 클 수도 있으니까 입력을 할 때 미리 더해뒀다가 정렬로 구한 값과 비교해 더 큰 값을 출력해주면 된다.

 

* 30 (mid) : 어떤 수가 주어졌을 때, 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만드는 문제다.

10610번: 30

- 두가지만 생각해주면 된다. 3의 배수이므로 모든 자리값의 합이 3의 배수인지, 그리고 0이 한개 이상 존재하는지 확인한다. 조건을 만족하면 최댓값이므로 내림차순 정렬해서 출력하면 된다.

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

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

	int c = 0;
	bool zero = false;
	for (int i = 0; i < n.size(); i++) {
		c += n[i] - '0';
		if (n[i] == '0') zero = true;
	}
	if (c % 3 == 0 && zero == true) {
		sort(n.begin(), n.end());
		reverse(n.begin(), n.end());
		for (int i = 0; i < n.size(); i++) cout << n[i];
	}
	else {
		cout << -1;
	}
	cout << '\n';
	return 0;
}

 

* 병든 나이트 (mid) : 조건에 맞게 방문할 수 있는 칸의 최대 개수를 구하는 문제다.

1783번: 병든 나이트

- 생각 해줘야 할 조건이 많다. 좀 걸리더라도 확실하게 체크하고 문제 푸는 습관을 기르자.

- 이동할 수 있는 방법은 4가지인데, 모두 어쨌든 오른쪽으로 움직인다. 세로의 길이에 따라 움직일 수 있는 범위도 달라진다. 오른쪽으로는 계속 가야하니까, 세로를 기준으로 생각해보자.

- 우선 세로 길이가 1이라면, 이동할 수 있는 방법은 없다. 최소 1칸의 여유공간은 있어야 뭐라도 한다. 따라서 세로 길이가 1이면 이동할 수 있는 곳은 지금 있는 곳, 1곳이다.

- 세로 길이가 2라면 어떻게 될까? 2, 4 경로로 번갈아서 이동할 수 있다. 하지만 이동 횟수가 4번 이상이 되면 모든 방법을 한 번씩 사용해야 하는데 높이가 딸려서 그렇게는 못 한다. 따라서 방문할 수 있는 곳의 최댓값은 4이고, 4보다 작은 값은 적절하게 계산해주면 된다.

- 세로 길이가 3이상이면 더이상 움직임의 제약은 없다. 1,2,3,4를 모두 한번씩 사용하려면 가로가 최소 7은 되어야 한다. 그 다음부터는 아무 경로나 가도 된다. 최대한 많이 가려면, 오른쪽으로 1칸만 가는 1,4를 번갈아 이용하면 되겠다. 이 또한 적절하게 계산해서 값을 구해주면 된다.

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

int main()
{
	int n, m;
	cin >> n >> m;

	int ans;
	if (n == 1) {
		ans = 1;
	}
	else if (n == 2) {
		ans = min(4, (m - 1) / 2 + 1);
	}
	else {
		if (m >= 7) {
			ans = m - 2;
		}
		else {
			ans = min(4, m);
		}
	}
	cout << ans << '\n';
	return 0;
}

- 간단해보이지만, 생각을 차근차근 잘 해야 풀 수 있는 문제였다.

 

* AB (high) : 조건을 만족하는 문자열을 찾는 문제다. 이번 챕터에서 제일 까다로웠다.

12970번: AB

- i < j 이면서 s[i] == 'A', s[j] == 'B'를 만족하는 (i,j) 쌍이 k개 있는 s를 구하는 문제다. 조건을 만족하면 아무거나 출력하면 된다. 관건은 A, B의 위치를 어떻게 배치하느냐였다.

- 먼저 생각해줘야 할 것은 A와 B의 개수다. 문자열의 길이가 n이므로 a(A개수) + b(B 개수) = n 을 만족해야 한다. 또한, a와 b는 조건을 만족하는 쌍을 0개에서 a*b개까지 만들 수 있다. B를 먼저 배열하고 구하고자 하는 개수에 맞게 A를 집어넣으면 된다. A를 전부 B 배열보다 먼저 놓으면 a*b개, 전부 B 배열의 뒤에 놓으면 0개이다.

- 이 성질을 이용해서 코딩을 해주면 되는데.. 이것도 좀 생각해줘야 했다.

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

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

	for (int a = 0; a <= n; a++) {
		int b = n - a;
		if (a*b < k) continue;
		vector<int> cnt(b + 1);
		for (int i = 0; i < a; i++) {
			int x = min(k, b);
			cnt[x] += 1;
			k -= x;
		}
		for (int i = b; i >= 0; i--) {
			for (int j = 0; j < cnt[i]; j++) cout << 'A';
			if (i > 0) cout << 'B';
		}
		cout << '\n';
		return 0;
	}
	cout << -1 << '\n';
	return 0;
}

- 우선 조건을 만족하는 a, b를 구한다. 그리고 B 사이 사이에 들어갈 A의 개수를 기록하는 배열을 만들어준다. 사이 사이에 들어가는 거니까 크기는 b+1이 되겠다.

- 계산을 편하게 하려면 역순으로 생각해주고, 출력은 다시 역순으로 해주자.

요런식으로

 

* A와 B (mid) : A, B로만 이루어진 두 수 S, T가 주어지고 S를 T로 바꿀 수 있는지 확인하는 문제다.

12904번: A와 B

- 문자열을 뒤집는다고 했는데, 멍청하게 각 문자열을 A에서 B로 카드 뒤집듯이 뒤집었다. 한참을 바보짓 했다.. 그게 아니라 문자열 자체를 뒤집는 거였다.

- 제시된 두 조건이 맨 뒤에 각각 A 추가, 문자열 뒤집기 후 B 추가 형태다. 이를 이용해 뒤에서부터 추적하면 어떤 조건을 사용했는지 역추적 할 수 있다는 것이 포인트였다.

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

int main()
{
	string s, t;
	cin >> s >> t;

	int idx = t.size() - 1;
	while (s.size() != t.size()) {
		if (t[idx] == 'A') {
			t.pop_back();
		}
		else {
			t.pop_back();
			reverse(t.begin(), t.end());
		}
		idx--;
	}

	if (s == t) {
		cout << 1;
	}
	else {
		cout << 0;
	}
	cout << '\n';

	return 0;
}

- 코드는 간단했지만, 잘 생각해줘야 하는 문제다.. 그리디는 다 그런 식인 것 같다.

-

꾸준함에 장사 없다. 잘 하고 있다.

언젠가 번뜩 깨닫는 날이 올 때까지.. 정진 또 정진.

정리 끝!