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 문제 푸셨으면 공짜 문제이니 가져가세요~
투 포인터에 대한 설명까지 하면 글이 길어질 것 같아.. 예전에 찍은 강의로 대체할게요!
5.1 투 포인터
youtu.be/L5Aoq447YWM
kau-algorithm.tistory.com
이 문제는 왼쪽 포인터 (가장 최솟값) - 오른쪽 포인터 (가장 최댓값)으로 두고 시작합니다.
만약 둘의 합이 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";
}