부트캠프 28일차 후기

오늘로 주특기 강의 주차가 마무리 되고, 다음 주부터 팀 프로젝트 주차에 들어선다.

어제로 기본 과제에 추가 과제까지 다한 오늘은 비교적 쉬엄쉬엄 공부를 해서 적을 것이 많진 않다.

 

일단 CodeKata는 오늘도 2문제를 풀었다. 역시나 첫 풀이가 중요하는 것을 증명하듯, 첫 문제의 풀이를 잘못해서 다시 푸는 데에 시간을 소모하였다. 또 덤으로 SQL 문제를 25문제 정도 풀었다. SQL 문제는 오랜만이라서, 몇몇 개념이 갑자기 안 떠올랐기에 구글링을 거쳤고, 이 중 가장 기억에 남는 것은 String 관련 SQL문이다.

 

SQL문에서 문자열 컬럼에 특정 문자열이 포함되어 있는지를 확인하는 SQL은 WHERE 컬럼 LIKE CONCAT('%', "문자열", '%')이다. 여기서 %는 와일드카드로, 앞뒤에 어떠한 문자열이 와도 상관 없도록 붙여준다. 또한 String을 대문자로 바꿔주는 UPPER와 소문자로 바꿔주는 LOWER가 존재한다.

 

간만에 난이도 있는 Greedy 알고리즘 문제를 스스로 풀어서, 여기에 한 번 적어보려고 한다.

https://www.acmicpc.net/problem/15708

15708번: 미네크래프트

 

이 문제를 보자마자 바로 떠오른 풀이는 다음과 같다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
int N, T, P, K[100001], pos = 0, t = 0, ans = 0;
ll calc(pi p)
{
	return (ll)p.first + (ll)(abs(pos - p.second) * P);
}
class cmp
{
public:
	bool operator()(pi &p1, pi &p2)
	{
		ll c1 = calc(p1);
		ll c2 = calc(p2);
		if (c1 == c2) return abs(pos - p1.second) > abs(pos - p2.second);
		return c1 > c2;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> T >> P;
	priority_queue<pi, vector<pi>, cmp> pq;
	for (int i = 0; i < N; i++)
	{
		cin >> K[i];
		pq.push({ K[i], i });
	}
	while (!pq.empty() && calc(pq.top()) + t <= T)
	{
		t += calc(pq.top());
		pos = pq.top().second;
		pq.pop();
		++ans;
	}
	cout << ans << '\n';
}

이 풀이는 현재 위치에서 각 땅을 파는 총 시간(이동 시간 + 파는 시간)들을 우선순위 큐에 넣고, 가장 적게 시간이 걸리는 땅으로 이동해서 땅을 판다는 식이다. 그리고 제출 결과, 훌륭하게 채점 0%대에서 틀렸다. 즉, 풀이가 틀렸단 이야기이다.

 

새로운 풀이에 대해 고민을 하던 중, 내가 이전에 풀었던 Greedy 문제가 하나 떠올랐다.

 

https://www.acmicpc.net/problem/2138

2138번: 전구와 스위치

이 문제는 인덱스를 처음부터 훑으면서 이전의 전구와 지금의 전구를 비교해서 스위치를 누름 여부를 결정하는 Greedy한 문제이다. 문득, 내가 고민하고 있는 문제 풀이를 이 문제와 유사하게 풀 수 있지 않을까? 란 생각이 든 순간, 한가지 깨닫게 되었다.

 

그것은 즉슨, 어차피 맨 왼쪽에서 시작하므로, 오른쪽으로 가다가, 괜히 왼쪽으로 갈 필요가 없다는 사실이다. 왼쪽으로 가면 괜히 시간을 더 소모하게 되므로, 굳이 왼쪽으로 가지 않고, 내가 오른쪽으로 가는 도중에 땅을 파면 되지 않냐?는 것이다. 그럼, 내가 왼쪽에서 오른쪽으로 순서대로 움직일 때, 팔 땅을 어떻게 결정하지란 문제에 직면하게 되는데, 여기서 우선 순위 큐가 등장한다. 내가 왼쪽에서 오른쪽으로 갈떄, 일단 땅을 판다고 가정을 하고, 판 시간을 우선 순위 큐에 넣는다. 그리고 어떤 땅을 파면서 시간이 초과 된다면, 우선 순위 큐에서 가장 시간이 많이 걸리는 것들을 빼서 땅 판 사실을 없애고, 시간을 확보한다! 란 풀이가 번뜩였다.

 

여기서 주의점은 오른쪽 끝까지 가지 않고, 최대로 땅을 팔 수도 있으므로 중간중간 팔 수 있는 땅의 양을 확인한다는 점이다. 그렇게 떠오른 아이디어를 바탕으로 적은 코드는 다음과 같다.

#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
int N, T, P, K[100001], t = 0, ans = 0;
long long S = 0;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> T >> P;
	priority_queue<int> pq;
	for (int i = 0; i < N; i++) cin >> K[i];
	for (int i = 0; i < N; i++)
	{
		S += K[i] + ((i == 0) ? 0 : P);
		pq.push(K[i]);
		while (!pq.empty() && S > T)
		{
			S -= pq.top();
			pq.pop();
		}
		ans = max(ans, (int)pq.size());
	}
	cout << ans << '\n';
}

그렇게 "맞았습니다!!"를 마주하게 된다. 코드 자체는 쉽지만, 난이도 있는 Greedy 알고리즘 답게, 떠올리기 어려운 아이디어였다. "전구와 스위치"는 구글링을 통해서 해답을 알게된 문제인데, 만약 이 문제를 접하지 않았다면 이 문제 답도 떠올리기 쉽지 않았을 것 같다.

 

다음 주는 오랜만에 팀 프로젝트에 들어선다. 마음 단단히 먹고 프로젝트에 임하도록 하자.