백준 알고리즘 중급 - 분할정복 (도전)

도전 문제답게 어렵다.

어느정도 고민의 시간을 가지고, 분석한다는 마음으로 코드를 따라갔다.

정리 시작!

-

* 스카이라인 (high) : 건물의 정보가 주어졌을 때, 스카이라인을 구하는 문제다.

1933번: 스카이라인

- 처음엔 높은 건물부터 정렬해서 위치별로 중복되지 않게 스카이라인을 구해보려고 했다. 하지만 건물의 위치와 높이 범위가 1억이나 되고.. 중복을 표시할 수 있는 방법이 없기에.. 무리였다. 분할 정복이니 머지를 이용할텐데.. 어떤 식으로 이용할지 감이 잘 안 잡혔다.

- 먼저 입력한 값을 왼쪽 x축을 기준으로 정렬한 뒤, 머지 소트를 해준다. start와 end의 값이 같으면, 즉 건물이 하나라면 그 건물의 왼쪽 x축과 높이, 그리고 오른쪽 x축과 0을 입력해서 리턴한다.

- 두 그룹을 비교할 때, 왼쪽 x축이 더 작은 수부터 먼저 입력을 시도한다. 현재 왼쪽 x축을 x에, 그리고 현재 높이와 이전 높이 중 더 큰 것을 h에 넣고 append 함수에서 스카이라인에 포함될 수 있는 좌표인지 확인해준다.

- append에서는 만약 하나 이상의 값이 들어가있다고 할 때, 마지막으로 들어간 항의 높이가 현재 높이와 같다면 이는 높이가 변하는 지점이 아니므로 건너 뛴다. 또한, 마지막으로 들어간 항의 x축이 현재 x축과 같다면 이는 새로운 지점의 추가 없이 높이만 바꿔주고 건너 뛴다. 두 예외에 해당하지 않는다면 새로운 스카이라인으로 추가해주면 된다. append 함수가 사실상 이 문제의 키포인트였다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
using RESULT = vector< pair<int, int>>;

struct bd {
	int left, height, right;
};

void append(RESULT &ans, pair<int, int> p) {
	int n = ans.size();
	if (n > 0) {
		if (ans[n - 1].second == p.second) {
			return;
		}
		if (ans[n - 1].first == p.first) {
			ans[n - 1].second = p.second;
			return;
		}
	}
	ans.push_back(p);
}

RESULT merge(RESULT &l, RESULT &r) {
	RESULT ans;
	int h1 = 0;
	int h2 = 0;
	int i = 0;
	int j = 0;
	while (i < l.size() && j < r.size()) {
		auto &u = l[i];
		auto &v = r[j];
		if (u.first < v.first) {
			int x = u.first;
			h1 = u.second;
			int h = max(h1, h2);
			append(ans, make_pair(x, h));
			i += 1;
		}
		else {
			int x = v.first;
			h2 = v.second;
			int h = max(h1, h2);
			append(ans, make_pair(x, h));
			j += 1;
		}
	}
	while (i < l.size()) {
		append(ans, l[i]);
		i += 1;
	}
	while (j < r.size()) {
		append(ans, r[j]);
		j += 1;
	}
	return ans;
}

RESULT go(vector<bd> &a, int start, int end) {
	if (start == end) {
		RESULT ans = { { a[start].left, a[start].height },{ a[start].right, 0 } };
		return ans;
	}
	int mid = (start + end) / 2;
	auto l = go(a, start, mid);
	auto r = go(a, mid + 1, end);
	return merge(l, r);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<bd> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].left >> a[i].height >> a[i].right;
	}
	sort(a.begin(), a.end(), [](auto &u, auto &v) {
		return make_tuple(u.left, u.right, u.height) < make_tuple(v.left, v.right, v.height);
	});

	auto ans = go(a, 0, n - 1);
	for (auto &p : ans) {
		cout << p.first << ' ' << p.second << ' ';
	}
	cout << '\n';
	return 0;
}

- using result = ~; 로 귀찮은 작업을 줄이는 법도 하나 배웠다. auto를 적재적소에 쓰면 코딩이 빨라진다는 사실도..

- 코딩 테스트 문제가 아마 이정도 난이도려나..? 이런 문제는 언제쯤 내 힘으로 풀어낼 수 있을까...ㅠ,ㅠ 열심히 허자..

 

* 가장 가까운 두 점 (high) : 여러 좌표가 주어지고, 그중 가장 가까운 두 점의 (거리)^2를 구하는 문제다.

2261번: 가장 가까운 두 점

- 범위가 작으면 O(n^2)로 풀어버리면 되지만.. 어림도 없다.

- 이 또한 머지 소트로 접근하는데, 여러 단계를 거쳐서 범위를 좁혀 나간다. 먼저 좌표의 수가 3개 이하면 그냥 모든 점을 다 검사해보는 게 빠르니 예외 처리를 해준다. 이외의 경우에는 x축을 기준으로 정렬한 뒤에, mid를 기준으로 왼쪽 부분과 오른쪽 부분에서 각각 가장 가까운 두 점의 거리를 구한다. 그리고 그중에서도 더 짧은 거리를 최솟값으로 잡아준다.

- 그렇게 mid를기준으로 양쪽에 각각 존재하는 두 점 사이 거리의 최솟값 m을 구했다면 a[mid]와의 x축 거리가 m보다 작은 좌표만 따로 저장한다. 그럼 가장 가까운 두 점을 구할 준비가 끝났다.

- 따로 저장한 배열을 이번엔 y축을 기준으로 정렬한다. y축 간의 거리가 m보다 작다면, 두 점의 거리를 구하고 m과 비교해서 최솟값을 구한다. 이를 반복하면 전체 점 중에서 가장 가까운 두 점의 거리가 나온다.

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

struct pos {
	int x, y;
};

bool cmp_x(const pos &a, const pos &b) {
	return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}

bool cmp_y(const pos &a, const pos &b) {
	return make_pair(a.y, a.x) < make_pair(b.y, b.x);
}

int dist(pos a, pos b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int check_all(vector<pos> &a, int start, int end) {
	int ans = -1;
	for (int i = start; i <= end - 1; i++) {
		for (int j = i + 1; j <= end; j++) {
			int d = dist(a[i], a[j]);
			if (ans == -1 || ans > d) {
				ans = d;
			}
		}
	}
	return ans;
}

int closest(vector<pos> &a, int start, int end) {
	int n = end - start + 1;
	if (n <= 3) {
		return check_all(a, start, end);
	}
	int mid = (start + end) / 2;
	int left = closest(a, start, mid);
	int right = closest(a, mid + 1, end);
	int ans = min(left, right);

	vector<pos> b; // 각각 구한 최솟값의 최솟값보다 가까운 거리의 값만 저장
	for (int i = start; i <= end; i++) {
		int d = a[i].x - a[mid].x;
		if (d*d < ans) {
			b.push_back(a[i]);
		}
	}

	sort(b.begin(), b.end(), cmp_y); // y좌표 기준 정렬
	int m = b.size();
	for (int i = 0; i < m - 1; i++) {
		for (int j = i + 1; j < m; j++) {
			int y = b[j].y - b[i].y;
			if (y*y < ans) { // 범위 안에 들어오지 않으면 거리 안 재봐도 됨.
				int d = dist(b[i], b[j]);
				if (ans > d) {
					ans = d;
				}
			}
			else {
				break;
			}
		}
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<pos> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].x >> a[i].y;
	}

	sort(a.begin(), a.end(), cmp_x); // x좌표 기준 정렬
	cout << closest(a, 0, n - 1) << '\n';
	return 0;
}

- 복잡해 보이지만 구조적으로 이해하기는 쉬운 문제였다. 머지 소트를 이용해 순차적으로 범위를 좁혀 가는 요령을 잘 기억해두자.

-

어려운 문제였지만, 뭔가 말로 풀어서 정리하니까 이해가 더 잘 되는 것 같다.

코드가 복잡해질 수록 말로 표현하기가 쉽지 않은데, 이런 연습도 많이 해봐야 할 것 같다.

오늘도 고생했다.

정리 끝!