백준 BOJ 11514번 : Refract Facts
문제 난이도 : Gold V
알고리즘 분류 : 이분 탐색, 물리학
비행기의 고도, 잠수함의 깊이, 비행기와 잠수함의 x축 거리, 공기와 물의 굴절률이 주어졌을 때 특정 각도를 구하는 문제이다.
각도를 알기 위해 알아야 하는 변수는 굴절 지점의 위치이다.
스넬의 법칙에 따르면 빛의 굴절 각도의 sin값의 비가 두 매질의 굴절률의 비와 같다.
따라서 이를 이용하여 다음과 같이 수식을 정리해줄 수 있다.
이제 a에 대한 이분 탐색을 수행해서 답을 구해주면 된다.
사실은 a 값에 따른 수식의 값이 극값을 가지지 않음을 보여야 하는데, 문제만 풀 거라면 사실 큰 의미 없다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(2);
while(true) {
double d, h, x, n1, n2; cin >> d >> h >> x >> n1 >> n2;
if(d == 0 && h == 0 && x == 0 && n1 == 0 && n2 == 0) break;
double l = 0, r = x;
while(l + 1e-3 < r) {
double m = (l + r)/2;
double val = (m * sqrt((x - m)*(x - m) + d*d)) / ((x - m) * sqrt(m*m + h*h));
if(val < n2/n1) l = m;
else r = m;
}
cout << atan(d/(x - l)) * 180.0 / M_PI << "\n";
}
}
백준 BOJ 12899번 : 데이터 구조
문제 난이도 : Platinum IV
알고리즘 분류 : 세그먼트 트리
1번 쿼리에 대해 그룹에 자연수 x를 추가하고, 2번 쿼리에 대해 그룹에서 x번째로 작은 수를 출력하고 삭제하는 쿼리들을 수행하는 문제이다.
쿼리의 수는 200만 이하, x의 범위가 200만 이하인데 여기서 주목할 것은 x의 범위가 200만 이하이므로 모든 가능한 x에 대한 노드를 가지고 있는 세그먼트 트리를 만들 수 있다는 것이다.
x번째 리프 노드는 x를 가지고 있으면 1, 아니면 0을 저장하는 구조를 형성하고 또한 부모 노드는 자식 노드의 구간 합을 저장하도록 하여 부모 노드의 값을 가지고 k번째로 작은 수를 log 시간에 찾아낼 수 있다.
원소의 추가 및 삭제를 하는 과정에서는 거쳐가는 모든 노드에 +1 또는 -1을 하여 간단히 갱신해줄 수 있다. (원소가 하나 추가되면 해당 구간은 구간 합이 +1이 되고, 삭제되면 해당 구간은 구간 합이 -1이 되기 때문이다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int Max = 2e6;
vector<int> v(Max * 4);
void f(int n, int b, int e, int idx) {
if(idx < b || e < idx) return;
v[n]++;
if(b == e) return;
f(n*2, b, (b+e)/2, idx);
f(n*2 + 1, (b+e)/2 + 1, e, idx);
}
int g(int n, int b, int e, int cnt) {
v[n]--;
if(b == e) return b;
if(cnt <= v[n*2]) return g(n*2, b, (b+e)/2, cnt);
else return g(n*2 + 1, (b+e)/2 + 1, e, cnt - v[n*2]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
while(N--) {
int Q, x; cin >> Q >> x;
if(Q == 1) f(1, 1, Max, x);
else if(Q == 2) cout << g(1, 1, Max, x) << "\n";
}
}
백준 BOJ 13023번 : ABCDE
문제 난이도 : Gold V
알고리즘 분류 : 그래프 탐색 (DFS)
어떤 한 노드에서 중간 노드를 중복하지 않고 4번 이동하여 도달할 수 있는 노드가 존재하는지 물어보는 문제이다.
여기서 말하는 중복 없이 4번 이동하여 도달한다는 것은 거리가 4라는 뜻이 아니다.
더 짧은 길이 있더라도 4번의 이동으로 돌아서 도달할 수 있으면 존재하는 것이 된다.
그렇다면 단순 BFS로 해결하는 문제가 아니라는 뜻이다.
문제의 힌트는 N과 M의 범위에 있는데, 둘 모두 2,000이하이므로 O(N^2) 또는 O(M^2) 또는 O(NM) 등이 가능하다.
이 문제를 해결하는 가장 간단한 방법은 DFS를 이용하여 깊이를 탐색하되 탐색 이후 스택과 같은 원리로 vis의 check를 다시 false로 바꾸면서 탐색하는 것이다.
그렇게 한다면 한 노드에서 방문할 수 있는 모든 경로로 다른 노드들을 방문할 수 있게 된다.
물론 이러한 탐색의 시작점을 모든 노드에 대해 수행해야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M;
vector<vector<int>> adj;
vector<bool> vis;
bool check = false;
void f(int x, int cnt) {
vis[x] = true;
if(cnt == 4) {
check = true;
return;
}
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(!vis[y]) f(y, cnt + 1);
}
vis[x] = false;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M;
adj.resize(N);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=0; i<N; i++) {
vis.clear();
vis.resize(N);
f(i, 0);
if(check) {
cout << 1 << "\n";
return 0;
}
}
cout << 0 << "\n";
}
백준 BOJ 5081번 : Constellations
문제 난이도 : Gold V
알고리즘 분류 : 분리 집합
N개 별의 좌표가 주어지고 각 별은 가장 가까운 별과 같은 별자리라고 할 때, 몇 개의 별자리가 존재하는지를 구하는 문제이다.
N이 크지 않으므로 각 별에 대해 가장 가까운 거리의 별을 모두 체크해줄 수 있다.
union find를 이용하여 만약 같은 집합이 아니라면 같은 집합으로 저장한다.
parent를 저장한 집합을 정렬 후 중복을 제거한 뒤 벡터의 사이즈를 출력해주는 방식으로 답을 구하였다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
int f(int x) {
if(x == v[x]) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
for(int t=1; ; t++) {
int N; cin >> N;
if(N == 0) break;
v.clear();
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
vector<pair<int, int>> u(N+1);
for(int i=1; i<=N; i++) cin >> u[i].first >> u[i].second;
for(int i=1; i<=N; i++) {
int Min = INT_MAX, idx;
for(int j=1; j<=N; j++) {
if(i == j) continue;
Min = min(Min, (int)(pow(u[i].first - u[j].first, 2) + pow(u[i].second - u[j].second, 2)));
}
for(int j=1; j<=N; j++) {
if(i == j) continue;
if(pow(u[i].first - u[j].first, 2) + pow(u[i].second - u[j].second, 2) == Min) {
if(f(i) != f(j)) v[f(i)] = f(j);
}
}
}
vector<int> w;
for(int i=1; i<=N; i++) w.push_back(f(i));
sort(w.begin(), w.end());
w.erase(unique(w.begin(), w.end()), w.end());
cout << "Sky " << t << " contains " << w.size() << " constellations.\n";
}
}
백준 BOJ 5996번 : Heat Wave
문제 난이도 : Gold V
알고리즘 분류 : 데이크스트라 (다익스트라)
N개의 마을, M개의 경로의 출발점과 도착점과 거리, 전체 경로의 출발점과 도착점이 주어질 때 출발점에서 도착점으로 가는 최단 거리를 구하는 문제이다.
간단한 데이크스트라 문제로, 다익스트라 알고리즘을 사용하여 정석적으로 풀이하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> p;
vector<vector<p>> adj;
vector<int> dis;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, sour, dest; cin >> N >> M >> sour >> dest;
adj.resize(N+1);
dis.resize(N+1, INT_MAX);
while(M--) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
priority_queue<p, vector<p>, greater<p>> pq; // <dis, node>
pq.push({0, sour});
while(!pq.empty()) {
int dis1 = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(dis[cur] < dis1) continue;
for(int i=0; i<adj[cur].size(); i++) {
int nex = adj[cur][i].first;
int dis2 = adj[cur][i].second;
if(dis1 + dis2 < dis[nex]) {
dis[nex] = dis1 + dis2;
pq.push({dis[nex], nex});
}
}
}
cout << dis[dest] << "\n";
}
백준 BOJ 13397번 : 구간 나누기 2
문제 난이도 : Gold IV
알고리즘 분류 : 이분 탐색
N개의 수로 이루어진 수열을 M개 이하의 구간으로 나누어 각 구간의 최댓값과 최솟값의 차이가 특정 값 이하가 되게 하고 싶어 할 때, 이 특정 값의 최댓값을 구하는 문제이다.
매개 변수 탐색을 이분 탐색으로 찾아줄 수 있는 문제이며, 답을 m이라고 가정하고 최댓값과 최솟값이 m이 넘어갈 경우 새 그룹을 만들어주는 방식으로 하여 m으로 가정했을 때 그룹이 몇 개 생기는지를 확인하여 이 값이 M 이하이면 값을 줄여보고 아니면 늘리는 방식으로 답을 구해줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int l = 0, r = 1e4, ans = 1e4;
while(l <= r) {
int m = (l + r)/2;
int cnt = 1, Min = 1e4, Max = 0;
for(int i=0; i<N; i++) {
Min = min(Min, v[i]);
Max = max(Max, v[i]);
if(Max - Min > m) {
cnt++;
Min = v[i];
Max = v[i];
}
}
if(cnt <= M) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
백준 BOJ 18402번 : RUN
문제 난이도 : Gold V
알고리즘 분류 : 데이크스트라 (다익스트라)
감옥의 N개 cell과 도착지 cell, 제한 시간, 그리고 M개의 경로(출발 cell, 도착 cell, 이동 시간)가 주어질 때 각 cell마다 1명씩 죄수가 있다고 하면 제한 시간 내에 도착 cell로 이동할 수 있는 죄수의 수를 구하는 문제이다. (이 때 경로는 단방향이다.)
경로가 단방향이고 사람들이 한 cell로 모이는 상황이므로, 데이크스트라를 활용하기 위해 문제를 거꾸로 생각해서 도착 cell에서 제한 시간동안 얼마나 많은 cell에 도달할 수 있는지를 count 해주면 된다.
물론 이 때 경로가 단방향이므로 역으로 연결해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> p;
vector<vector<p>> adj;
vector<int> dis;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, sour, time, M; cin >> N >> sour >> time >> M;
adj.resize(N+1);
dis.resize(N+1, INT_MAX);
while(M--) {
int a, b, c; cin >> a >> b >> c;
adj[b].push_back({a, c});
}
dis[sour] = 0;
priority_queue<p, vector<p>, greater<p>> pq; // <dis, node>
pq.push({0, sour});
while(!pq.empty()) {
int dis1 = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(dis[cur] < dis1) continue;
for(int i=0; i<adj[cur].size(); i++) {
int nex = adj[cur][i].first;
int dis2 = adj[cur][i].second;
if(dis1 + dis2 < dis[nex]) {
dis[nex] = dis1 + dis2;
pq.push({dis[nex], nex});
}
}
}
int ans = 0;
for(int i=1; i<=N; i++) {
if(dis[i] <= time) ans++;
}
cout << ans << "\n";
}
백준 BOJ 5590번 : 船旅
문제 난이도 : Gold V
알고리즘 분류 : 데이크스트라 (다익스트라)
0번 쿼리에 대해서는 특정 정점부터 특정 정점까지의 거리를 구하고, 1번 쿼리에 대해서는 새 간선을 추가하는 문제이다.
데이크스트라 알고리즘을 이용하면 모든 거리 배열을 초기화하고 거리를 다시 구해야하는데, 쿼리의 수가 100개 이하로 아주 적으므로 데이크스트라 구현부를 함수로 옮겨서 일일이 다시 구해줘도 시간 초과가 발생하지 않는다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> p;
int N, M;
vector<vector<p>> adj;
vector<int> dis;
void f(int sour, int dest) {
dis.clear();
dis.resize(N+1, INT_MAX);
dis[sour] = 0;
priority_queue<p, vector<p>, greater<p>> pq; // <dis, node>
pq.push({0, sour});
while(!pq.empty()) {
int dis1 = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(dis[cur] < dis1) continue;
for(int i=0; i<adj[cur].size(); i++) {
int nex = adj[cur][i].first;
int dis2 = adj[cur][i].second;
if(dis1 + dis2 < dis[nex]) {
dis[nex] = dis1 + dis2;
pq.push({dis[nex], nex});
}
}
}
if(dis[dest] != INT_MAX) cout << dis[dest] << "\n";
else cout << -1 << "\n";
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M;
adj.resize(N+1);
while(M--) {
int Q; cin >> Q;
if(Q == 1) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
else if(Q == 0) {
int sour, dest; cin >> sour >> dest;
f(sour, dest);
}
}
}
백준 BOJ 6054번 : Relay race
문제 난이도 : Gold V
알고리즘 분류 : 데이크스트라 (다익스트라)
1번 소가 출발하여 도착하면 다른 소들을 출발시키고, 이 소들도 달린 후 도착하여 다른 소들을 출발시키고, ... 하는 과정을 거쳐 모든 소들의 레이스가 끝나는데 걸리는 시간을 구하는 문제이다.
이 문제는 데이크스트라 알고리즘으로 풀이할 수 있는데, 소가 레이스를 하는데 걸리는 시간은 거리로, 소가 다른 소를 출발 시키는 것은 두 소 번호 사이를 간선으로 연결한다고 생각해주면 된다.
1번 소부터의 모든 소들의 거리 중 최댓값을 구하면 거의 풀리는데, 문제는 그 값에 마지막 소가 달리는 시간까지 더해주어야 한다.
최대 유량 알고리즘처럼 가상의 N+1번 노드를 연결해주면 간단할 것 같긴 한데 그러다가 오히려 귀찮아질 수도 있을 것 같아서 그냥 반례들을 복잡하게 처리했다.
특히 소가 1마리만 있는 경우는 따로 처리해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> p;
vector<vector<p>> adj;
vector<int> dis;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
adj.resize(N+1);
dis.resize(N+1, INT_MAX);
vector<int> w(N+1);
for(int i=1; i<=N; i++) {
int a, b; cin >> a >> b;
while(b--) {
int c; cin >> c;
adj[i].push_back({c, a});
}
w[i] = a;
}
if(N == 1) {
cout << w[1] << "\n";
return 0;
}
priority_queue<p, vector<p>, greater<p>> pq; // <dis, node>
pq.push({0, 1});
while(!pq.empty()) {
int dis1 = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(dis[cur] < dis1) continue;
for(int i=0; i<adj[cur].size(); i++) {
int nex = adj[cur][i].first;
int dis2 = adj[cur][i].second;
if(dis1 + dis2 < dis[nex]) {
dis[nex] = dis1 + dis2;
pq.push({dis[nex], nex});
}
}
}
int ans = 0;
for(int i=1; i<=N; i++) {
if(dis[i] != INT_MAX) ans = max(ans, dis[i] + w[i]);
}
cout << ans << "\n";
}
백준 BOJ 24391번 : 귀찮은 해강이
문제 난이도 : Gold V
알고리즘 분류 : 분리 집합
연결된 건물들의 번호가 주어지고, 수업 시간표가 주어질 때 연결되지 않은 건물 사이의 이동이 몇 번 발생하는지 구하는 문제이다.
disjoint set을 사용하여 먼저 건물들을 연결시켜주고, 시간표를 입력받아 인접한 두 수업이 연결된 건물인지를 확인하여 그렇지 않은 경우 하나씩 count 해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
int f(int x) {
if(x == v[x]) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
while(M--) {
int a, b; cin >> a >> b;
if(f(a) != f(b)) v[f(a)] = f(b);
}
vector<int> u(N);
for(int i=0; i<N; i++) cin >> u[i];
int ans = 0;
for(int i=1; i<N; i++)
if(f(u[i-1]) != f(u[i])) ans++;
cout << ans << "\n";
}
백준 BOJ 10677번 : It's All About the Base
문제 난이도 : Gold V
알고리즘 분류 : 이분 탐색
두 수가 주어지고 각각 같은 수를 10 ~ 15,000 중 하나의 진수로 나타낸 수라고 할 때, 두 진수를 찾는 문제이다.
우선 진수의 범위를 알려줬는데 15,000 이하이므로 O(N^2) 시간에 풀기에는 애매하다.
따라서 한 수에 대해서는 진수를 완전 탐색하고, 동시에 해당 진수로 나타내어진 수를 다른 진수로 찾을 수 있는지의 여부를 이분 탐색으로 찾아줄 수 있다.
즉, 입력된 두 수 a, b에 대해 a를 10 ~ 15,000인 i진수로 나타낸 뒤 이 나타내어진 수를 b를 j진수로 나타낸 수와 같은지에서 j를 이분 탐색으로 찾는 것이다.
문제에서 각 테스트케이스에 대해 고유한 정답이 있다고 하였으므로 별도의 예외 처리를 해줄 필요는 없다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
string a, b; cin >> a >> b;
for(int i=10; i<=15000; i++) {
int x = (a[0] - '0')*i*i + (a[1] - '0')*i + (a[2] - '0');
int l = 10, r = 15000;
while(l <= r) {
int m = (l + r)/2;
int y = (b[0] - '0')*m*m + (b[1] - '0')*m + (b[2] - '0');
if(y == x) {
cout << i << " " << m << "\n";
break;
}
if(y < x) l = m + 1;
else r = m - 1;
}
}
}
}
백준 BOJ 20917번 : 사회적 거리 두기
문제 난이도 : Gold V
알고리즘 분류 : 이분 탐색
1차원 좌표에서 N개의 좌석의 위치가 주어질 때 M명이 앉는 최소 거리의 최댓값을 구하는 문제이다.
최소 거리를 변수로 놓고 매개 변수를 탐색하는 이분 탐색 문제이다.
벡터 v에 위치를 저장하고 정렬한 뒤 오름차순 간격을 벡터 u에 저장했다.
이 문제의 경우 다른 문제와 이분 탐색의 while문 내의 구현이 조금 달라야 하는데, 왜냐하면 거리가 가정한 값 이하로 들어오는게 아닌 이상으로 들어와야 하기 때문에 sum + u[i] 값이 m 값을 넘어가면 sum = 0, cnt++로 갱신해주어야 한다. (sum = u[i]가 아니다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
vector<int> u(N-1);
for(int i=0; i<N-1; i++) u[i] = v[i+1] - v[i];
int l = 1, r = INT_MAX, ans = 1;
while(l <= r) {
int m = (l + r)/2;
int cnt = 1, sum = 0;
for(int i=0; i<N-1; i++) {
if(sum + u[i] >= m) {
sum = 0;
cnt++;
}
else sum += u[i];
}
if(cnt >= M) {
ans = max(ans, m);
l = m + 1;
}
else r = m - 1;
}
cout << ans << "\n";
}
}
백준 BOJ 6018번 : Tea Time
문제 난이도 : Gold V
알고리즘 분류 : 분리 집합
N마리의 소들이 있고 M번의 1대1 만남이 있었으며 K개의 쿼리로 두 소가 건너건너 아는 사이인지를 물어볼 때 이를 구하는 문제이다.
간단한 분리 집합 문제로 만남이 있을 때마다 두 집합이 다른 집합이면 연결을 시켜주고, K개의 쿼리에 대해 두 소의 연결 관계를 조사하여 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
int f(int x) {
if(x == v[x]) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
while(M--) {
int a, b; cin >> a >> b;
if(f(a) != f(b)) v[f(a)] = f(b);
}
while(K--) {
int a, b; cin >> a >> b;
if(f(a) == f(b)) cout << "Y\n";
else cout << "N\n";
}
}
백준 BOJ 9140번 : Přeprava materiálu
문제 난이도 : Gold V
알고리즘 분류 : 데이크스트라 (다익스트라)
N개의 도시와 M개의 경로, 그리고 출발점과 도착점이 주어질 때 출발점에서 도착점으로 가는 최단 경로를 구하는 문제이다.
간단하고 정석적인 다익스트라 문제이다.
정석과 똑같이 구현해주면 되지만 이 문제는 여러 개의 테스트케이스가 입력으로 주어지므로 while문을 하나 추가하고 adj 벡터와 dis 벡터를 매번 초기화해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> p;
vector<vector<p>> adj;
vector<int> dis;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N, M, sour, dest; cin >> N >> M >> sour >> dest;
if(N == 0 && M == 0 && sour == 0 && dest == 0) break;
adj.clear();
adj.resize(N+1);
dis.clear();
dis.resize(N+1, INT_MAX);
while(M--) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
dis[sour] = 0;
priority_queue<p, vector<p>, greater<p>> pq; // <dis, node>
pq.push({0, sour});
while(!pq.empty()) {
int dis1 = pq.top().first;
int cur = pq.top().second;
pq.pop();
if(dis[cur] < dis1) continue;
for(int i=0; i<adj[cur].size(); i++) {
int nex = adj[cur][i].first;
int dis2 = adj[cur][i].second;
if(dis1 + dis2 < dis[nex]) {
dis[nex] = dis1 + dis2;
pq.push({dis[nex], nex});
}
}
}
cout << dis[dest] << "\n";
}
}
백준 BOJ 5033번 : Money Matters
문제 난이도 : Silver I
알고리즘 분류 : 분리 집합
N명의 사람들의 손익값이 주어지고, M개의 친구 관계가 주어질 때, 친구 관계로 연결된 사람들끼리 손익을 주고받을 수 있다고 할 때 모든 사람들의 손익을 0으로 만들 수 있는지를 구하는 문제이다.
이 문제는 다양한 풀이 방법이 있을 것으로 보이는데 나는 일단 분리 집합을 이용하여 푸는 것이 가장 간단해 보였다.
친구 관계인 그룹끼리 같은 집합으로 묶고, 손익을 한 그룹의 최상위 노드로 모두 더했을 때, 모든 합이 0이 되기만 하면 POSSIBLE을 출력해줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
v.resize(N);
for(int i=0; i<N; i++) v[i] = i;
vector<int> u(N);
for(int i=0; i<N; i++) cin >> u[i];
while(M--) {
int a, b; cin >> a >> b;
if(f(a) != f(b)) v[f(a)] = f(b);
}
vector<int> w(N);
for(int i=0; i<N; i++) w[f(i)] += u[i];
bool check = true;
for(int i=0; i<N; i++)
if(w[i] != 0) check = false;
if(check) cout << "POSSIBLE\n";
else cout << "IMPOSSIBLE\n";
}
백준 BOJ 23372번 : Ice Growth
문제 난이도 : Silver I
알고리즘 분류 : 누적 합, 이분 탐색
얼음 두께가 온도가 5도 올라갈 때 1cm 감소하고, 5도 내려갈 때 1cm 증가한다고 할 때 M개의 쿼리(얼음 두께) 이상의 값을 가지는 날의 수를 구하는 문제이다.
얼음 두께는 첫 날부터 누적해서 변화하며, 얼음의 두께가 음수가 될 수 없다.
누적 합 배열을 입력되는 두께의 마이너스 값을 더해주면서 구해준 뒤, 각 쿼리에 대해 이분 탐색으로 답을 구해주면 된다.
다만 이 문제의 포인트는 정수형 자료형으로 풀이하기 위해 각 쿼리의 두께를 5배로 바꾸어 탐색을 해주면 편하다는 것과, 얼음의 두께가 마이너스가 될 수 없기 때문에 음수가 될 경우 sum = max(sum - x, 0)으로 갱신을 해주어야 한다는 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
int sum = 0;
vector<int> v(N);
for(int i=0; i<N; i++) {
int x; cin >> x;
sum = max(sum - x, (int)0);
v[i] = sum;
}
sort(v.begin(), v.end());
while(M--) {
int x; cin >> x;
cout << v.end() - lower_bound(v.begin(), v.end(), x*5) << " ";
}
cout << "\n";
}
백준 BOJ 6031번 : Feeding Time
문제 난이도 : Silver I
알고리즘 분류 : 그래프 탐색 (DFS, BFS)
'.'으로 나타내어진 땅이 8방향으로 이어질 수 있다고 할 때 가장 큰 땅의 덩어리의 크기를 구하는 문제이다.
정석적인 그래프 탐색 문제로 DFS 또는 BFS를 활용하여 풀이할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M, cnt;
vector<vector<char>> v;
vector<vector<bool>> vis;
void f(int x, int y) {
vis[x][y] = true;
cnt++;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
for(int i=0; i<8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if(v[nx][ny] != '.' || vis[nx][ny]) continue;
f(nx, ny);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> M >> N;
v.resize(N, vector<char>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
vis.resize(N, vector<bool>(M));
int ans = 0;
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
if(v[i][j] != '.' || vis[i][j]) continue;
cnt = 0;
f(i, j);
ans = max(ans, cnt);
}
cout << ans << "\n";
}
백준 BOJ 14326번 : Jane's Flower Shop (Small), 백준 BOJ 14327번 : Jane's Flower Shop (Large)
문제 난이도 : Siver II ~ Silver I
알고리즘 분류 : 이분 탐색
초기 비용과 복리 비율, 그리고 월별 수입의 값이 주어질 때 주어진 수식을 만족하는 rate의 값을 구하는 문제이다.
수식에 그대로 대입만 하여 매개 변수 r을 구하면 되므로, 이분 탐색이 적절하다.
최종 답은 오차가 10^(-9)보다 작아야 하므로, r - l의 값이 10^(-9)보다 작아질 때까지 이분 탐색을 수행하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(9);
int T; cin >> T;
for(int t=1; t<=T; t++) {
int N; cin >> N;
vector<double> v(N+1);
for(int i=0; i<N+1; i++) cin >> v[i];
v[0] *= -1;
double l = 0, r = 2;
while(l + 1e-10 < r) {
double m = (l + r)/2;
double sum = 0;
for(int i=0; i<N+1; i++) sum += v[N-i] * pow(m, i);
if(sum <= 0) r = m;
else l = m;
}
cout << "Case #" << t << ": " << (l - 1) << "\n";
}
}
백준 BOJ 4030번 : 포켓볼
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
a와 b가 주어질 때 a < x+1 < b이고 x가 삼각수이고 x+1이 사각수(제곱수)인 x의 수를 구하는 문제이다.
a와 b의 범위가 0 ~ 1e9이므로 풀이 시간을 줄이기 위한 방법을 생각해야 한다.
먼저 x+1이 제곱수인 x를 잡고 그 다음 x가 삼각수인지를 체크해주면 시간을 많이 줄일 수 있을 것이다. (제곱수는 루트 개수만큼만 존재하므로)
따라서 a < i × i < b인 i에 대해 반복문을 돌려주고 i × i - 1이 삼각수 m × (m+1) / 2를 만족하는 m이 존재하는지를 찾아 count 해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
for(int t=1; ; t++) {
int a, b; cin >> a >> b;
if(a == 0 && b == 0) break;
int ans = 0;
for(int i=1; i*i<b; i++) {
if(i*i <= a) continue;
int l = 1, r = 1e9;
bool check = false;
while(l <= r) {
int m = (l + r)/2;
if(m*(m+1)/2 == i*i - 1) {
check = true;
break;
}
if(m*(m+1)/2 < i*i - 1) l = m + 1;
else r = m - 1;
}
if(check) ans++;
}
cout << "Case " << t << ": " << ans << "\n";
}
}
백준 BOJ 6170번 : World Cup Noise
문제 난이도 : Silver III
알고리즘 분류 : DP
0과 1로만 이루어진 수열에 대해 1이 연속 2번 나타나지 않는 길이 N인 수열의 수를 구하는 문제이다.
길이 i인 수열에 대해 규칙을 만족하면서 0으로 끝나거나 1로 끝나는 것을 나눠서 저장한다.
dp[i][0]을 0으로 끝나는 수열, dp[i][1]을 1로 끝나는 수열이라고 하자.
그러면 dp[i][0] = dp[i-1][0] + dp[i-1][1]이고 dp[i][1] = dp[i-1][0]이므로 이 점화식을 이용하여 답을 구할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int dp[50][2] = {{}, {1, 1}};
for(int i=2; i<45; i++) {
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
int T; cin >> T;
for(int t=1; t<=T; t++) {
int N; cin >> N;
cout << "Scenario #" << t << ":\n";
cout << dp[N][0] + dp[N][1] << "\n";
cout << "\n";
}
}
백준 BOJ 1392번 : 노래 악보
문제 난이도 : Bronze II
알고리즘 분류 : 구현
0초부터 시작하여 각 음표의 길이가 주어질 때, M개의 쿼리에 대해 특정 초에 몇 번 음표가 연주되고 있는지를 구하는 문제이다.
음표의 수는 최대 100개이고 각 음표의 길이 또한 최대 100이므로, 10,000 크기의 배열에 값들을 저장해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(10001);
int cur = 0;
for(int i=1; i<=N; i++) {
int x; cin >> x;
while(x--) v[cur++] = i;
}
while(M--) {
int x; cin >> x;
cout << v[x] << "\n";
}
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 풀이 : 오늘도 그래프 탐색 문제 220726 (0) | 2022.07.26 |
|---|---|
| 백준 BOJ 풀이 : BFS 문제들 위주 풀이 (그래프 탐색) 220725 (0) | 2022.07.25 |
| 백준 BOJ 풀이 : 이분 탐색 문제들 마저 해치우기 (220723) (0) | 2022.07.23 |
| 백준 BOJ 풀이 : 이분 탐색 문제들 위주 풀이 (220722) (0) | 2022.07.22 |
| 백준 BOJ 풀이 : 이분 탐색, 조합론(완전순열, 카탈란 수) 문제 등 (220721) (0) | 2022.07.21 |