알고리즘 분할정복 거듭제곱, 투포인터 등 알고리즘 문제 풀이 221001
풀이한 문제들 중에서 인상적인 문제만 몇 개 뽑아서 정리한다.
문제 알고리즘은 무작위로 선정하였다.
백준 BOJ 25569번 : My뷰 꾸미기
문제 난이도 : Platinum IV
알고리즘 분류 : 조합론, 분할 정복을 이용한 거듭제곱
N개의 (a, b)쌍에 대해 min(a, b) = c라고 할 때, (a C 1 x b C 1) + (a C 2 x b C 2) + ... + (a C c x b C c)의 합을 구하는 문제이다.
N과 a, b는 30만 이하이다.
각 항을 팩토리얼과 분모는 페르마의 소정리 + 분할 정복을 이용한 거듭제곱으로 계산이 가능하나, 항이 매우 많아 시간 초과에 걸리게 된다.
이 경우 항을 줄여주어야 하는데, (a C 1 x b C 1) + (a C 2 x b C 2) + ... + (a C c x b C c) = (a C 1 x b C b - 1) + (a C 2 x b C b - 2) + ... + (a C c x b C b - c) = ((a + b) C b) - 1이므로 (a+b개 중에 1 ~ b개를 고르는 경우의 합이니까) 하나의 컴비네이션 값만 계산해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mod = 1e9 + 7;
vector<int> fac(6e5 + 1);
int fp(int ba, int ex) {
int ret = 1;
while(ex > 0) {
if(ex % 2 == 1) ret = (ret * ba) % mod;
ba = (ba * ba) % mod;
ex /= 2;
}
return ret;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
fac[0] = 1;
for(int i=1; i<=6e5; i++) fac[i] = (fac[i-1] * i) % mod;
int N; cin >> N;
int ans = 1;
while(N--) {
int a, b; cin >> a >> b;
int c = min(a, b);
int tmp = (fac[a+b] * fp(fac[c], mod - 2)) % mod;
tmp = (tmp * fp(fac[a+b-c], mod - 2)) % mod;
tmp = (tmp - 1 + mod) % mod;
ans = (ans * tmp) % mod;
}
cout << ans << "\n";
}
백준 BOJ 20366번 : 같이 눈사람 만들래?
문제 난이도 : Gold III
알고리즘 분류 : 투 포인터
N개의 정수 중에 4개를 선택하여 두 개, 두 개씩 짝지은 합의 차의 최소를 구하는 문제이다.
먼저 떠올릴 수 있는 방법은 N C 2개를 고른 배열을 만들어 두 배열에서 이분 탐색을 하는 것인데, 이 경우 각 합에서 중복되는 원소가 포함되어 있는지를 알 방법이 없다.
따라서 N이 600 이하이므로, 이중 for문을 돌려주고 이 때 각 i와 j 사이에서 l, r에 대한 투 포인터 알고리즘을 사용하여 v[i] + v[j]와 v[l] + v[r]을 가지고 비교하여 답을 구해주면 된다.
최종 시간 복잡도는 O(N^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];
sort(v.begin(), v.end());
int ans = LLONG_MAX;
for(int i=0; i<N; i++)
for(int j=i+3; j<N; j++) {
int l = i+1, r = j-1;
while(l < r) {
int dif = abs((v[i] + v[j]) - (v[l] + v[r]));
ans = min(ans, dif);
if((v[l] + v[r]) < (v[i] + v[j])) l++;
else r--;
}
}
cout << ans << "\n";
}
백준 BOJ 3090번 : 차이를 최소로
알고리즘 분류 : 이분 탐색, 그리디
문제 난이도 : Platinum III
길이 N인 수열에서 하나의 수를 골라 1만큼 감소시키는 비용이 1이라고 할 때, 비용을 M 이하로 하여 수열의 인접한 숫자간의 차이값을 최소로 했을 때의 배열을 구하는 문제이다.
인접한 수의 차이를 m 이하로 잡고 비용을 M 이하로 사용할 수 있는지 체크하면서 이분 탐색으로 풀이하면 된다.
m을 설정했으면 값들을 그리디하게 바꾸어주는 것이 최선이다.
따라서 0에서부터 N-1까지 이동하면서 오른쪽 수가 m보다 많이 크다면 비용에 v[i+1] - (v[i] + m)을 더해주고 v[i+1] = v[i] + m으로 바꿔준다.
반대 방향 인접 값들도 마찬가지로 N-1에서 0까지 이동하면서 왼쪽 수가 m보다 많이 크다면 비용에 v[i-1] - (v[i] + m)을 더해주고 v[i-1] = v[i] + 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 = 1e9;
vector<int> ans;
while(l <= r) {
int m = (l + r) / 2;
vector<int> u(v);
int sum = 0;
for(int i=0; i<N-1; i++) {
if(u[i] + m < u[i+1]) {
sum += u[i+1] - (u[i] + m);
u[i+1] = u[i] + m;
}
}
for(int i=N-1; i>0; i--) {
if(u[i] + m < u[i-1]) {
sum += u[i-1] - (u[i] + m);
u[i-1] = u[i] + m;
}
}
if(sum <= M) {
ans = u;
r = m - 1;
}
else l = m + 1;
}
for(int i=0; i<ans.size(); i++) cout << ans[i] << " ";
cout << "\n";
}
백준 BOJ 2812번 : 크게 만들기
문제 난이도 : Gold III
알고리즘 분류 : 그리디, 스택
N자리 수에서 M개의 수를 지워 만들 수 있는 가장 큰 수를 구하는 문제이다.
뭔가 코드포스에서 많이 나올 것 같은 유형의 문제라서 풀어보았다.
빈 문자열에 N자리 수를 앞에서부터 하나씩 추가하다가 추가할 수가 문자열의 맨 뒷 문자보다 크다면 맨 뒷 문자를 지우고 추가해주는 과정을 반복하고, M을 1 줄여준다.
만약 이 과정이 끝나도 M이 0보다 크다면, 뒤의 M자리는 지워졌다고 생각하고 앞의 s.length() - 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;
string str; cin >> str;
string ans = "";
for(int i=0; i<str.length(); i++) {
while(ans.length() > 0 && str[i] > ans.back() && M > 0) {
ans.pop_back();
M--;
}
ans += str[i];
}
ans = ans.substr(0, ans.length()-M);
cout << ans << "\n";
}
백준 BOJ 5447번 : Stock Market
문제 난이도 : Silver II
알고리즘 분류 : DP
구간 합이 최대인 부분의 양 끝 주소를 구하는 문제이다.
단, 그러한 구간이 여러 개 있을 경우 시작 주소가 작은 것을 구해야 한다.
DP를 이용한 구간 합 최대를 구하는 알고리즘 문제이다.
이에 대해서는 이 블로그 카테고리의 알고리즘 구현 코드 모음에 정리되어 있으니 참고 바란다.
#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; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
vector<int> dp(N), le(N);
dp[0] = v[0];
for(int i=1; i<N; i++) {
if(dp[i-1] >= 0) {
dp[i] = dp[i-1] + v[i];
le[i] = le[i-1];
}
else {
dp[i] = v[i];
le[i] = i;
}
}
int Max = INT_MIN, l, r;
for(int i=0; i<N; i++)
if(dp[i] > Max) {
Max = dp[i];
l = le[i] + 1;
r = i + 1;
}
cout << l << " " << r << "\n";
}
}
백준 BOJ 10892번 : Divide into triangle
문제 난이도 : Silver IV
알고리즘 분류 : 기하학, 구성적
2차원 좌표 평면 상의 3N개의 점이 주어지고, 이들 중 일직선 상에 있는 세 점이 없다고 할 때, 3개씩 N개의 쌍을 만들어 각 쌍의 점들의 삼각형이 서로 겹치지 않게 하는 조합을 구하면 된다.
y 좌표, x 좌표 순으로 정렬하여 (반대로 정렬해도 상관없음) 순서대로 3개씩 뽑아주면 절대로 겹치지 않음을 알 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int x, y, n; };
bool cmp(s a, s b) {
if(a.y != b.y) return a.y > b.y;
else if(a.x != b.x) return a.x < b.x;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<s> v(N*3);
for(int i=0; i<N*3; i++) {
cin >> v[i].x >> v[i].y;
v[i].n = i+1;
}
sort(v.begin(), v.end(), cmp);
for(int i=0; i<N*3; i+=3)
cout << v[i].n << " " << v[i+1].n << " " << v[i+2].n << "\n";
}
백준 BOJ 25694번 : Ramen
문제 난이도 : Silver IV
알고리즘 분류 : 그리디
길이 N인 라면의 맛에 해당하는 배열이 주어지고, 2l ≤ n인 l에 대해 a_1 ~ a_l이 모두 0보다 크다면 이 구간을 오른쪽으로 접어서 값을 합칠 수 있다고 할 때, 하나의 면을 길이가 1인 면으로 접을 수 있는지 구하는 문제이다.
길이 l만큼 접는 경우 그 구간은 모두 양수여야 하므로, 이는 결국 길이 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);
int N; cin >> N;
int cur = 0;
bool check = true;
while(N--) {
int x; cin >> x;
cur += x;
if(cur <= 0 && N > 0) check = false;
}
if(check) cout << "YES\n";
else cout << "NO\n";
}