4/3 모의 테스트 해설

푸시느라 고생하셨습니다~

 

 

문제 구성

• 백준 7795번 먹을 것인가 먹힐 것인가
• 백준 16948번 데스 나이트 
• 백준 2075번 N번째 큰 수
• 백준 2470번 두 용액

 

이번 문제 셋은 조금 덜 유명하지만 빈번히 나오는 힙(우선순위 큐), 이분 탐색, 투 포인터 유형에 

항상 나오는 bfs 문제 하나를 출제하였습니다.

 

 

 

1. 백준 7795번 먹을 것인가 먹힐 것인가

 

이분 탐색 유형의 문제입니다.

 

자칫 잘못 생각하면 브루트 포스를 떠올릴 수 있지만, 지금 스코어보드를 보니 그런 분들은 없는 것 같아서

따로 시간 복잡도에 대한 설명은 생략하고 코드만 올려두겠습니다.

 

참고로 예시 코드는 두 가지로, 하나는 이분 탐색을 직접 구현했고

나머지 하나는 그냥 lower_bound 함수를 사용해 풀었습니다.

 

혹시 upper, lower bound 를 처음 보신다면 한 번 구글링해 찾아보시는 걸 추천드려요!

 

 

소스 코드1 (.cpp) - 이분 탐색 구현

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int>a, b;

int bi_search(int x) {
	if (x <= b[0]) return 0;

	int left = 0, right = m - 1, mid = 0;
	int tmp = 0;
	while (left <= right) {
		mid = (left + right) / 2;
		if (b[mid] < x) {
			tmp = max(tmp, mid);
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return tmp + 1;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n >> m;
		a.resize(n); b.resize(m);

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

		sort(b.begin(), b.end());

		int ans = 0;

		for (int i = 0; i < n; i++) {
			ans += bi_search(a[i]);
		}

		cout << ans << "\n";
	}
	return 0;
}

 

 

소스 코드2 (.cpp) - lower_bound 함수 사용

 

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int>a, b;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n >> m;
		a.resize(n); b.resize(m);

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

		sort(b.begin(), b.end());

		int ans = 0;

		for (int i = 0; i < n; i++) {
			ans += lower_bound(b.begin(), b.end(), a[i]) - b.begin();
		}

		cout << ans << "\n";
	}
	return 0;
}

 

 

2. 백준 16948번 데스 나이트 

 

최소 이동 횟수를 구하는 전형적인 bfs 문제입니다.

 

오랜만에 푸시는 분들을 위해 손좀 푸시라고 내드렸습니다 ㅎㅎ

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[222][222];
int dist[222][222];

int dy[] = { -2, -2, 0, 0, 2, 2 };
int dx[] = { -1, 1, -2, 2, -1, 1 };
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	int r1, r2, c1, c2;
	cin >> r1 >> c1 >> r2 >> c2;
	
	memset(dist, -1, sizeof(dist));

	dist[r1][c1] = 0;

	queue<pair<int, int> >q;
	q.push({ r1, c1 });

	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (int k = 0; k < 6; k++) {
			int nr = r + dy[k];
			int nc = c + dx[k];
			if (0 > nr || nr >= n || 0 > nc || nc >= n) continue;
			if (dist[nr][nc] == -1 || dist[nr][nc] > dist[r][c] + 1) {
				dist[nr][nc] = dist[r][c] + 1;
				q.push({ nr, nc });
			}
		}
	}
	
	cout << dist[r2][c2] << "\n";
	return 0;
}

 

 

3. 백준 2075번 N번째 큰 수

 

여러 풀이가 있을 수 있겠지만, 우선순위 큐를 이용한 풀이가 가장 웰노운한 것 같네요. 

 

문제의 핵심은 메모리 제한입니다. 

입력으로 주어지는 N이 1,500 이기 때문에 원소는 최대 1500 * 1500 = 225만이 들어오게 되는데

보통 int 형으로 받는다고 했을 때 4bytes * 225만 = 약 900만 bytes = 9,000 kb = 9 mb

 

어라? 되네?

 

 

근데 안 받아지네요!

 

그 이유는.. 225만 개를 받는 입력 버퍼 메모리도 포함해야 되기 때문이라네요 ㅠㅠ

 

참고 : www.acmicpc.net/board/view/36675

 

 

아무튼 문제 조건이 적나라하게 메모리를 제한하고 있기 때문에 무식하게 모두 받고 정렬하면

제출한 코드가 정답인지 안 가르쳐주는 코테에서는 발표날까지 두려움에 떨게 될 거예요!

 

하지만 이 문제는 굳이 모두 저장할 필요가 없습니다.

 

우선 크기 n짜리 최소 힙 (루트가 모든 노드들 중 최솟값)을 만들어

입력으로 들어오는 첫 n개의 원소를 받아줍니다.

 

그렇다면 일단 n개중 n번째 큰 수는 루트가 되겠죠! (가장 작은 수)

 

이후 숫자가 들어올 때마다 루트 노드와 비교합니다. 만약 루트 노드보다 현재 보고 있는 수가 작다면

이 수는 현재까지 n번째 큰 수보다 작은 것이니 비교할 필요가 없어요.

 

만약 그렇지 않다면 루트 노드를 pop 하고 현재 보고 있는 수를 push 합니다.

그렇게 되면 최소 힙 구조 상 n번째 큰 수가 다시 탐색돼서 루트 노드로 올라오겠죠

 

이 과정을 끝까지 한 후 루트 노드를 출력하면 됩니다.

 

메모리는 항상 n개의 최소 힙만 존재했기 때문에 충분하겠네요!

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	priority_queue<int, vector<int>, greater<int> >pq;

	int n; cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int tmp; cin >> tmp;
			if (pq.size() < n) pq.push(tmp);
			else {
				if (pq.top() > tmp) continue;
				else {
					pq.pop();
					pq.push(tmp);
				}
			}
		}
	}
	cout << pq.top() << "\n";
	return 0;
}

 

 

 

4. 백준 2470번 두 용액

 

투 포인터 문제 유형입니다.

 

원래 정렬 안 하는 2467번 용액 문제를 내드리려다 헷갈려서 잘못 냈네요 ㅠㅠ

 

아무튼 둘 다 투 포인터로 푸는 문제이고, 2470 문제 푸셨으면 공짜 문제이니 가져가세요~

 

투 포인터에 대한 설명까지 하면 글이 길어질 것 같아.. 예전에 찍은 강의로 대체할게요!

 

kau-algorithm.tistory.com/105

5.1 투 포인터

 

이 문제는 왼쪽 포인터 (가장 최솟값) - 오른쪽 포인터 (가장 최댓값)으로 두고 시작합니다.

 

만약 둘의 합이 0보다 크다면, 배열은 정렬되어있는 상태이기 때문에

오른쪽 포인터를 왼쪽으로 한 칸 움직여줘야 합니다. (수를 줄여야 합니다.)

 

만약 이 논리를 깨뜨리려면, 현재 오른쪽 포인터와 매칭 되는 왼쪽 포인터보다 작은 포인터가 있어야겠죠. (둘의 합이 0보다 컸으므로)

 

1. 왼쪽 포인터가 초기값이라면 -> 더 이상 왼쪽 포인터보다 작은 수는 없습니다.

2. 초기값이 아니라면 -> 이미 확인했습니다. 왼쪽 포인터가 초기값이 아니라면 둘의 합이 0보다 작은 상황이 발생했을 것이고, 그 결과 우리는 이전보다 최적을 찾기 위해 왼쪽 포인터를 지금과 같은 위치에 옮긴 것이니까요

 

반대로 둘의 합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 한 칸 움직여주면 됩니다. (수를 키워야 합니다)

 

 

만약 모든 수가 양수 또는 음수이면 어떤 상황이 발생할까요?

 

만약 모든 수가 양수라면 가장 작은 두 수를 합치는 게 최선이겠죠.

위 로직대로라면 항상 두 수의 합이 0보다 크므로 오른쪽 포인터를 계속 왼쪽으로 움직이다 최선의 수를 찾겠네요.

 

만대로 모든 수가 음수라면 왼쪽 포인터를 오른쪽으로 움직이면서 최선의 수를 찾게 됩니다.

 

 

소스 코드(.cpp)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	int ans = 2000000001;
	sort(v.begin(), v.end());
	int left = 0, right = n - 1;
	int ans1 = 0, ans2 = 0;
	while (left < right)
	{
		int sum = v[left] + v[right];
		if (ans > abs(sum)) {
			ans1 = v[left]; ans2 = v[right];
		}
		ans = min(ans, abs(sum));
		if (sum > 0) {
			right--;
		}
		else if (sum < 0) {
			left++;
		}
		else {
			break;
		}
	}
	cout << ans1 << " " << ans2 << "\n";
}