백준 BOJ 알고리즘 공부 일기 (오프라인 쿼리 포함) 220829
백준 BOJ 13306번 : 트리
문제 난이도 : Platinum IV
알고리즘 분류 : 오프라인 쿼리, 분리 집합
트리와 쿼리가 주어질 때, 각 쿼리에 대해 특정 간선을 지우거나 두 정점이 연결 상태인지를 구하는 문제이다.
오프라인 쿼리 문제인데, 오프라인 쿼리 문제는 주어진 쿼리 순서대로 처리를 하는 것이 아니라 문제를 효율적으로 풀 수 있게끔 쿼리의 순서를 재배치하여 풀이하는 방식의 문제를 말한다.
예를 들어 이 문제에서는 쿼리를 역순으로 배치한 뒤 분리 집합으로 노드들을 연결해가면서 풀어주면 아주 쉽게 풀 수 있다.
역순 배치가 아닌 다른 순서대로 푸는 문제도 있는 것 같던데 조만간 공부할 것이다. (예를 들면 mo's 알고리즘. 지금 제곱근 분할법 문제 몇 개는 풀어봤는데 mo's를 공부 안해서 못 풀고 있는 문제들이 많다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int Q, a, b; };
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;
vector<int> p(N+1);
for(int i=2; i<=N; i++) cin >> p[i];
M += N-1;
vector<s> q(M);
for(int i=0; i<M; i++) {
cin >> q[i].Q;
if(q[i].Q == 0) cin >> q[i].a;
else if(q[i].Q == 1) cin >> q[i].a >> q[i].b;
}
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
stack<bool> ans;
for(int i=M-1; i>=0; i--) {
if(q[i].Q == 0) {
if(f(q[i].a) != f(p[q[i].a])) v[f(q[i].a)] = f(p[q[i].a]);
}
else if(q[i].Q == 1) {
if(f(q[i].a) == f(q[i].b)) ans.push(true);
else ans.push(false);
}
}
while(!ans.empty()) {
if(ans.top()) cout << "YES\n";
else cout << "NO\n";
ans.pop();
}
}
백준 BOJ 10775번 : 공항
문제 난이도 : Gold II
알고리즘 분류 : 분리 집합
N개의 게이트가 있고, M개의 비행기가 각각 u_i번 이하의 게이트에 도킹할 수 있다고 할 때, 주어진 입력 순서대로 비행기가 도킹한다면 최대로 도킹할 수 있는 비행기의 수를 구하는 문제이다.
그리디하게 접근하여 u_i 이하의 도킹이 가능한 가장 큰 번호의 게이트에 도킹을 해준다.
그 다음, 같은 번호의 게이트에 비행기가 들어올 경우 그 이하의 최대 번호로 연결을 효율적으로 해주어야 하는데 여기서 분리 집합을 사용하면 수월하다.
f(u_i)번 게이트에 도킹 후 f(u_i)값을 f(u_i) - 1로 해주면 된다.
한 번 parent로 이동했을 때 그 게이트가 이미 차 있다고 하더라도 해당 게이트의 parent 역시 다른 게이트로 연결되어 있을 것이기 때문에 빈 게이트를 효율적으로 찾아줄 수가 있다.
도킹을 계속 하다가 만약 f(u_i) = 0일 경우 도킹이 더 이상 불가능한 것이므로 지금까지 연결한 비행기의 개수로 답을 얻어주면 된다.
#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+1);
for(int i=1; i<=N; i++) v[i] = i;
int ans = 0;
vector<int> u(M);
for(int i=0; i<M; i++) cin >> u[i];
for(int i=0; i<M; i++) {
int x = u[i];
if(f(x) == 0) break;
v[f(x)] = f(x) - 1;
ans++;
}
cout << ans << "\n";
}
백준 BOJ 1440번 : 타임머신
문제 난이도 : Bronze II
알고리즘 분류 : 브루트포스
시, 분, 초가 주어질 때 시, 분, 초의 순서를 바꾸어 (그대로인 것 포함) 읽어도 시, 분, 초의 범위에 해당하는 것의 개수를 구하는 문제이다.
next_permutation으로 3!가지 경우를 모두 확인해보면 된다.
다만 이 문제의 경우 두 값이 같은 경우도 있는데 next_permutation 함수는 이 경우를 건너뛰므로 모두 다른 값을 가지는 벡터 하나를 추가로 이용해주는 방법 등을 사용해야한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
vector<int> v(3);
char c;
cin >> v[0] >> c >> v[1] >> c >> v[2];
vector<int> u(3);
u[0] = 0, u[1] = 1, u[2] = 2;
int ans = 0;
while(true) {
if(v[u[0]] >= 1 && v[u[0]] <= 12 && v[u[1]] >= 0 && v[u[1]] <= 59 && v[u[2]] >= 0 && v[u[2]] <= 59) ans++;
if(!next_permutation(u.begin(), u.end())) break;
}
cout << ans << "\n";
}
백준 BOJ 7637번 : AAAAHH! Overbooked!
문제 난이도 : Bronze II
알고리즘 분류 : 브루트포스
24시간짜리 시간으로 주어진 N개의 시간 범위에 대해, 겹치는 것이 있는지 확인하는 문제이다.
24 x 60짜리 크기의 bool 변수를 이용하여 체크를 일일이 해주면서 새로 체크할 값에 이미 체크가 하나라도 되어있다면 conflict를, 그렇지 않다면 no conflict를 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N; cin >> N;
if(N == 0) break;
vector<bool> v(24*60);
bool check = true;
while(N--) {
string str; cin >> str;
int a = stoi(str.substr(0, 2));
int b = stoi(str.substr(3, 2));
int c = stoi(str.substr(6, 2));
int d = stoi(str.substr(9, 2));
for(int i=a*60+b; i<c*60+d; i++) {
if(v[i]) check = false;
v[i] = true;
}
}
if(check) cout << "no conflict\n";
else cout << "conflict\n";
}
}
백준 BOJ 8676번 : Figury
문제 난이도 : Bronze II
알고리즘 분류 : 브루트포스
주어진 N개의 수에 대해 3개 연속으로 다른 수가 나오는 경우가 있는지 체크하는 문제이다.
단순히 3개씩 묶어서 일일이 확인해보면 된다.
#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; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
bool check = false;
for(int i=2; i<N; i++)
if(v[i] != v[i-1] && v[i-1] != v[i-2] && v[i-2] != v[i]) check = true;
if(check) cout << "TAK\n";
else cout << "NIE\n";
}
백준 BOJ 9151번 : Starship Hakodate-maru
문제 난이도 : Bronze II
알고리즘 분류 : 브루트포스
N 이하이면서 가장 큰 a^3 + b x (b+1) x (b+2) / 6의 값을 구하는 문제이다.
2중 for문으로 N 이하의 범위에서 가능한 모든 조합을 다 확인해보면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N; cin >> N;
if(N == 0) break;
int ans = 0;
for(int i=0; i*i*i<=N; i++)
for(int j=0; i*i*i+j*(j+1)*(j+2)/6<=N; j++) ans = max(ans, i*i*i + j*(j+1)*(j+2)/6);
cout << ans << "\n";
}
}
백준 BOJ 9182번 : Biorhythms
문제 난이도 : Bronze II
알고리즘 분류 : 브루트포스
특성 a는 23일마다, 특성 b는 28일마다, 특성 c는 33일마다 발현되며 하나의 테스트케이스에 각 특성이 발현된 날짜, 그리고 현재 날짜가 주어질 때 다음 날부터 세 특성이 모두 발현되는 날 중 가장 가까운 날까지의 기간을 구하는 문제이다.
입력이 a b c d로 들어온다고 해보자.
그러면 x > d인 x에 대해 x % 23 = a % 23이고, x % 28 = b % 28이고, x % 33 = c % 23이라면 x는 d일 이후 세 특성이 모두 발현되는 날이다.
따라서 이러한 x 중 가장 작은 것을 답으로 얻어주면 된다.
#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, c, d; cin >> a >> b >> c >> d;
if(a == -1 && b == -1 && c == -1 && d == -1) break;
for(int i=d+1; i<=21252; i++) {
if(i % 23 == a % 23 && i % 28 == b % 28 && i % 33 == c % 33) {
cout << "Case " << t << ": the next triple peak occurs in " << i - d << " days.\n";
break;
}
}
}
}
백준 BOJ 9377번 : String LD
문제 난이도 : Bronze II
알고리즘 분류 : 브루트포스
N개의 문자열에 대해, 각 문자열의 맨 왼쪽 문자를 지우는 연산을 다음이 되기 전까지 반복한다.
1. 문자열의 길이가 1인 것이 발생
2. 두 문자열이 같은 것이 발생
이 때, 연산을 최대 몇 번 수행할 수 있는지 구하는 문제이다.
예를 들어 1번 연산을 수행하여 같은 문자열이 발생한다면 답은 0이다. (발생 이전까지만 반복해야하므로)
조건 그대로 체크만 해주면 된다.
같은 문자열이 있는 것은 sort 해준 뒤 v[i-1]과 v[i]를 비교해주면 된다.
다만 두 문자열이 같은 것이 발생했을 경우는 이미 연산을 수행한 이후이므로 연산 수행 횟수를 잘 계산해서 구해주어야 한다. (0번이면 상관 없지만, 1번 이상인 경우는 1 빼고 구해주어야 함)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int N; cin >> N;
if(N == 0) break;
vector<string> v(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; ; i++) {
sort(v.begin(), v.end());
bool check = false;
for(int j=0; j<N; j++)
if(v[j].length() == 1) check = true;
for(int j=1; j<N; j++)
if(v[j] == v[j-1]) check = true;
if(check) {
cout << i << "\n";
break;
}
for(int j=0; j<N; j++)
v[j] = v[j].substr(1, v[j].length()-1);
sort(v.begin(), v.end());
check = false;
for(int j=1; j<N; j++)
if(v[j] == v[j-1]) check = true;
if(check) {
cout << i << "\n";
break;
}
}
}
}
백준 BOJ 9161번 : Sir Bedavere’s Bogus Division Solutions
문제 난이도 : Bronze III
알고리즘 분류 : 브루트포스
한 숫자의 맨 뒷자리와 다른 숫자의 맨 앞자리가 같은3자리 숫자 abc와 cde가 있을 때, 공통되는 숫자를 지워 ab, de를 만들었을 때 abc / cde = ab / de인 수의 순서쌍을 모두 구하는 문제이다.
abc를 100 ~ 999, cde도 100 ~ 999 사이의 모든 경우를 확인해보면 된다.
#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 i=100; i<=999; i++)
for(int j=100; j<=999; j++) {
if(i % 10 != j / 100) continue;
if(i % 111 == 0) continue;
int a = i, b = j, c = i / 10, d = j % 100;
if(a * d == b * c)
cout << a << " / " << b << " = " << c << " / " << d << "\n";
}
}
백준 BOJ 9664번 : NASLJEDSTVO
문제 난이도 : Bronze III
알고리즘 분류 : 브루트포스
몇 개의 물건 중에서 1/N만큼을 (내림) 가져가고 남은 것이 M개일 때, 원래 있었던 것으로 가능한 최소/최대 물건의 수를 구하는 문제이다.
내림 처리를 하고 가져갔기 때문에 역으로 연산하기가 쉽지 않다.
따라서 범위를 넉넉하게 잡아서 x - x/N = M이면 x에 대해 최대, 최소를 갱신해주면 된다.
#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 Min = INT_MAX, Max = INT_MIN;
for(int i=1; i<=1e3; i++) {
if(i - i/N == M) {
Min = min(Min, i);
Max = max(Max, i);
}
}
cout << Min << " " << Max << "\n";
}
백준 BOJ 19751번 : Fractification
문제 난이도 : Bronze III
알고리즘 분류 : 브루트포스
네 정수 a, b, c, d가 주어질 때 a/b + c/d가 최소가 되도록 값들을 적절히 swap하는 문제이다.
next_permutation 함수를 이용하여 4! 가지의 경우를 모두 비교해보면 된다.
실수 연산에서 오차가 발생하지 않을까 했는데 다행히 극악의 테스트케이스는 없는 것 같다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
vector<double> v(4);
for(int i=0; i<4; i++) cin >> v[i];
sort(v.begin(), v.end());
vector<double> u;
double Min = INT_MAX;
while(true) {
if(v[0] / v[1] + v[2] / v[3] < Min) {
Min = v[0] / v[1] + v[2] / v[3];
u = v;
}
if(!next_permutation(v.begin(), v.end())) break;
}
for(int i=0; i<4; i++) cout << (int)u[i] << " ";
cout << "\n";
}
백준 BOJ 24348번 : ИЗРАЗ
문제 난이도 : Bronze III
알고리즘 분류 : 브루트포스
3개의 수가 주어질 때, +, -, * 를 최대 한 번만 사용하여 만들 수 있는 최댓값을 구하는 문제이다. (세 수의 순서를 바꿔도 된다.)
next_permutation을 이용하여 세 수의 순서를 바꾸고, 주어지는 수가 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);
vector<int> v(3);
for(int i=0; i<3; i++) cin >> v[i];
sort(v.begin(), v.end());
int ans = 0;
while(true) {
ans = max(ans, v[0] + v[1] * v[2]);
ans = max(ans, v[0] * v[1] + v[2]);
if(!next_permutation(v.begin(), v.end())) break;
}
cout << ans << "\n";
}