2021. 9. 30. 03:52ㆍ알고리즘/codeforce
A. Casimir's String Solitaire
- 수학 문제
- 주어진 문자열에서 아래의 두 연산중 하나를 수행한다.
- 임의의 A 와 B를 제거
- 임의의 B 와 C를 제거
- 이때 문자열을 ""로 만들 수 있으면 YES , 아니면 NO를 출력하는 문제이다.
- 해결방법은 간단하다.
- 문자열에서 ABC 각각의 개수를 세고 A + C = B 가 성립하면 ""로 만들 수 있다.
반성 - 주어진 입력의 크기를 보지 못하고 완전탐색으로 모든 경우의 수를 구하여 풀려고 했다. |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
string s;
cin >> s;
int alpha[3] = {0, 0, 0};
for (int i = 0; i < s.length(); i++)
{
alpha[s[i] - 'A']++;
}
if (alpha[0] + alpha[2] == alpha[1])
{
cout << "YES\n";
}
else
{
cout << "NO\n";
}
}
}
B. Shifting Sort
- 구현 문제
- 주어진 연산으로 배열을 정렬하는 문제
- 연산은 다음과 같다.
- 배열안에서 구간 [l, r] 을 정한뒤 왼쪽으로 쉬프팅하는 횟수 d를 정한다.
- 그 구간만 d번 쉬프팅한 뒤 그 구간만 배열을 업데이트한다.
- 이 문제의 핵심은 구간과 쉬프팅하는 횟수를 자신이 정해야한다는것이다.
- 선택정렬이나 삽입정렬 처럼 "이미 정렬된 구간" 을 만드는 방향으로 연산을 정하면 문제를 해결할 수 있다.
- 정렬되어 있지 않은 구간에서 최소값을 찾고 그 값을 그 구간의 맨 왼쪽으로 옮기면된다.
- rotate 함수를 %연산을 사용하여 구현할 수 있다. (또는 std::rotate)
반성 - 주어진 문제를 제대로 해석하지 못하여 '최소' 횟수를 구하는 문제인줄 알았다. |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
void rotate(vector<int> &el, int lo, int hi, int k)
{
vector<int> tmp(el.begin() + lo, el.begin() + hi);
auto it = tmp.end();
tmp.insert(it, el.begin() + lo, el.begin() + hi);
k %= (tmp.size() / 2);
for (int i = lo, h = k; i < hi; i++, h++)
{
el[i] = tmp[h];
}
}
int N;
vector<vector<int>> solve(vector<int> &el)
{
vector<vector<int>> ret;
for (int i = 0; i < N; i++)
{
int min = min_element(el.begin() + i, el.end()) - el.begin();
if (min != i)
{
rotate(el, i, N, min - i);
ret.push_back({i + 1, N, min - i});
}
else
{
continue;
}
}
return ret;
}
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> N;
vector<int> el;
el.resize(N);
for (int i = 0; i < N; i++)
{
cin >> el[i];
}
vector<vector<int>> els = move(solve(el));
cout << els.size() << "\n";
for (int i = 0; i < els.size(); i++)
{
for (int j = 0; j < els[i].size(); j++)
{
cout << els[i][j] << " ";
}
cout << "\n";
}
}
}
C. Ticks
- 구현 문제
- 주어진 2차원 배열을 주어진 패턴으로 만들 수 있는지 체크하는 문제이다.
- 이 문제는 오른쪽 아래에서부터 왼쪽 위에서부터 패턴을 그리면 문제를 해결할 수 있다.
- 탐색하면서 만약 '.' 를 만나게되면 바로 false 를 반환하게하고
- '*' 만 있으면 좌표들을 map에 넣어 마지막에 모든 '*'들의 개수와 같은지 확인하면된다.
반성 - 2d vector 에선 꼭 resize하기전에 clear를 해주자 |
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
vector<vector<char>> board;
int n, m, k;
vector<pair<int, int>> painted;
map<pair<int, int>, int> chck;
bool erase1(int i, int j, int d)
{
for (int h = 0; h <= d; h++)
{
if (i - h < 0 || j + h >= m || j - h < 0)
{
return false;
}
if (board[i - h][j + h] == '.' || board[i - h][j - h] == '.')
{
return false;
}
}
chck[{i, j}]++;
for (int h = 1; h <= d; h++)
{
chck[{i - h, j + h}]++;
chck[{i - h, j - h}]++;
}
return true;
}
string solve()
{
for (int i = painted.size() - 1; i >= 0; i--)
{
for (int h = k; h < n; h++)
{
// 밑에서부터 체크하므로
if (erase1(painted[i].first, painted[i].second, h) == false)
break;
}
}
if (chck.size() == painted.size())
{
return "YES";
}
return "NO";
}
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n >> m >> k;
board.clear();
board.resize(n, vector<char>(m));
painted.resize(0);
chck.clear();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> board[i][j];
if (board[i][j] == '*')
{
painted.push_back({i, j});
}
}
}
cout << solve() << "\n";
}
}
D. Productive Meeting
- 그리디 문제
- 각 사람마다 미팅을 할 수 있는 횟수가 정해져있다.
- 미팅은 두명씩 이루어진다.
- 이때 최대 몇번할 수 있는지와 누가 누구랑 미팅하는지 출력하는 문제이다.
- 사람들 중에서 가장 많이 미팅 횟수가 남은 두사람 TOP1, TOP2를 선택하면된다.
- 만약 어느 순간에서 TOP1와 임의의 사람 A를 선택해서
- 결과로 최대미팅횟수가 나왔다고 가정해보자.
- 그 순간에서 A와 TOP2 를 교체하면
- TOP2와 짝이었던 B는 A와 짝이 맺어지게되고
- TOP2 와 TOP1 짝이 맺어지게되며, 결과는 변하지 않는다.
- 즉, 손해가 없으므로 그때 그때 가장 많이 미팅 횟수가 남은 두사람을 선택하게되면
- 문제는 해결된다.
- 이때 최대값을 리턴해주는 max heap 자료구조를 사용하면 구현하기가 편하다.
(우선순위 큐)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
pq.push({a, i + 1});
}
vector<pair<int, int>> answer;
pair<int, int> top1, top2;
while (true)
{
top1 = pq.top();
if (top1.first == 0)
{
break;
}
pq.pop();
top2 = pq.top();
if (top2.first == 0)
{
break;
}
pq.pop();
pq.push({top1.first - 1, top1.second});
pq.push({top2.first - 1, top2.second});
answer.push_back({top1.second, top2.second});
}
cout << answer.size() << "\n";
for (int i = 0; i < answer.size(); i++)
{
cout << answer[i].first << " " << answer[i].second << "\n";
}
}
}
E1. Permutation Minimization by Deque
- deque 문제
- 주어진 입력에대해 순서대로 deque에 집어넣어 사전순으로 제일 앞에 오도록 출력하는 문제
- 입력하는 부분에서 front 와 값비교만 하면 문제는 해결된다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
deque<int> answer;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
if (!answer.empty() && answer.front() > a)
{
answer.push_front(a);
}
else
{
answer.push_back(a);
}
}
for (int i = 0; i < n; i++)
{
cout << answer[i] << " ";
}
cout << "\n";
}
}
E2. Array Optimization by Deque
- 그리디 문제
- 역방향의 개수가 최소가 되도록 deque를 구성하는 문제.
(inversion i < j and di > dj)
- 주어진 입력 a를 deque 에 넣는다.
- 이 때 front 와 back 둘중 하나를 선택을 할 수 있으며
- 역방향의 개수는 deque 안에있는 값들에 의해 정해진다.
- 즉, deque 가 어떻게 구성되는지 몰라도 된다는것이다.
- 그러므로 그때 그때 집어넣을때마다
- 그 값보다 작은값들의 개수 와 큰것들의 개수 중 작은쪽을 선택하면 문제를 풀 수 있다.
- 하지만 O(N)으로 모든 값을 비교하면 시간초과가 뜬다.
- 그러므로 시간 복잡도를 O(lgn)으로 줄여야하며
- 이를 수행할 수 있게 해주는 자료구조로 세그먼트 트리가 있다.
- 주어진 입력을 모두 다시 값을 매겨주어
(정렬 순으로 0~ : 구간을 설정하기가 편해진다 ex. LCA )
- 순서대로 세그먼트 트리에 넣어 구간을 구간에 포함된 원소의 수를 업데이트하면
- 시간 초과 없이 문제는 해결된다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <queue>
using namespace std;
struct RQ
{
using ll = int;
const ll OUT_OF_BOUNDS_ = 0;
int n;
vector<ll> range;
RQ(const vector<ll> &array)
{
n = array.size();
range.resize(n * 4 + 4);
init(array, 0, n - 1, 1);
}
ll op(ll a, ll b)
{
return a + b;
}
ll init(const vector<ll> &array, int left, int right, int node)
{
if (left == right)
return range[node] = array[left];
int mid = (left + right) / 2;
ll leftValue = init(array, left, mid, node * 2);
ll rightValue = init(array, mid + 1, right, node * 2 + 1);
return range[node] = op(leftValue, rightValue);
}
ll query(int left, int right, int node, int nodeLeft, int nodeRight)
{
if (right < nodeLeft || nodeRight < left)
return OUT_OF_BOUNDS_;
if (left <= nodeLeft && nodeRight <= right)
return range[node];
int mid = (nodeLeft + nodeRight) / 2;
return op(query(left, right, node * 2, nodeLeft, mid),
query(left, right, node * 2 + 1, mid + 1, nodeRight));
}
ll query(int left, int right)
{
return query(left, right, 1, 0, n - 1);
}
ll update(int index, ll newValue, int node, int nodeLeft, int nodeRight)
{
if (index < nodeLeft || nodeRight < index)
return range[node];
if (nodeLeft == nodeRight)
return range[node] = newValue;
int mid = (nodeLeft + nodeRight) / 2;
return range[node] = op(
update(index, newValue, node * 2, nodeLeft, mid),
update(index, newValue, node * 2 + 1, mid + 1, nodeRight));
}
ll update(int index, int newValue)
{
return update(index, newValue, 1, 0, n - 1);
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
long long answer = 0;
vector<int> v(n);
map<int, int> mp;
for (int i = 0; i < n; i++)
{
cin >> v[i];
mp[v[i]] = 1;
}
int value = 0;
for (auto &it : mp)
{
it.second = value++;
}
RQ rq(vector<int>(n, 0));
for (int i = 0; i < n; i++)
{
int mid = mp[v[i]];
int left = rq.query(0, mid - 1);
int right = rq.query(mid + 1, n - 1);
answer += min(left, right);
rq.update(mid, rq.query(mid, mid) + 1);
}
cout << answer << "\n";
}
}
F. Array Stabilization (AND version)
?
G. Minimal Coverage
- dp 문제
- 구간의 길이가 담겨진 배열 A가 입력으로 주어진다. (1<= A[i]<= 1000)
- 이때 첫번째 구간 (0, A[0]) 에서부터 순서대로 구간을 만들어 나간다.
- 이후 구간을 만드는 규칙은 다음과 같다.
- 구간은 start 와 end로 이루어진다. (첫번째구간에서 0은 start)
- start는 이전 구간의 end이다.
- 이전의 end 가 x, 구간의 길이가 d 이면 다음구간은 [x,x+d], [x−d,x] 중 하나가된다. (x+d 와 x-d 는 end)
- 이런 규칙에 의해 i = 0 ~ n-1 까지 순서대로 구간들을 만들고
- 만들어진 구간 전부를 커버할 수 있는 구간을 구할 수 있다.
- 이 구간의 길이를 최소화한 값을 출력해야 하는 문제이다.
- 풀이 (recursive)
(https://codeforces.com/contest/1579/submission/130442295 코드를 보고 작성한 풀이)
- 최소값을 구하는 문제이기 때문에, 모든 경우의 수를 구하고 그중 최소값을 선택하면 답을 낼 수 있다.
- 하지만 주어진 A의 크기는 10^4 이므로, 완전탐색하면 답을 내는데 오래걸릴것이다.
- 그러므로 중복된 계산을 피하는 dp 를 사용하는 방식으로 접근해봐야한다.
- 문제에서 주어진 정보중 하나인 '순서'
- 앞에서부터 차근차근 구간을 만들어간다는것.
- 즉, 배열의 '인덱스' 에서 만들어온 구간들이 다르지만
- 만약 구간을 구성해온 최소값과 최대값, 그리고 이 지점에서의 end 값이 같으면
- 그 이후에 오는 최적의값을 한번만 구하면 다시 계산하지 않아도 됨을 의미한다.
- 한 상태에 대해 두 부분문제로 나뉘므로
- 이를 식으로 나타내면 다음과 같을것이다.
dp = idx 에서 [lo, hi] 가 전체 구간을 포함하고 end 가 x일때 만 들 수 있는 전체 구간을 포함하는 최소의 길이.
dp[idx][lo][hi][x] = min(dp[idx + 1][min(lo, x)][max(hi, x+a[idx])][x + a[idx]
, dp[idx+1][min(lo, x- a[idx])][max(hi, x)][x - a[idx]] );
- 하지만 이 식은 정보가 너무 많으며 모두 저장하기위해선 많은 메모리가 필요하다.
- 그러므로 정보들을 압축해야하며 이는 상대적인 거리로 표현하여 줄일 수 있다.
- 즉,
base 에서 left 만큼 떨어진 거리로 x를 표현하는것이다.
- 다음 idx의 left는 left -a[idx] 또는 left+a[idx] 가 된다.
- 여기서 주의할점은 left - a[idx]이다.
- 왼쪽으로 구간이 확장 : left -a[idx] < 0 일때 , base 가 변경됨을 의미한다.
- 이부분을 예외 처리하면
- 우리가 구하고자하는 lo~hi 값은 우리가 들렀던 left 중에서의 최댓값이라 생각할 수 있으며
- 이는 다음과 같은 식을 세울 수 있다.
dp[idx][left] = base에서 left만큼 떨어진 거리에서 idx 이후부터 만들 수있는 left + right의 최소 길이.
dp[idx][left] = min(dp[idx+1][left + a[idx]] ,
(left >= a[idx]) ? max(left, dp[idx + 1][left - a[idx]] : INF))
- 문제는 왼쪽 구간으로의 확장을 예외처리 했다는것이다.
- 왼쪽 구간으로의 확장은 base를 업데이트 시켜줘야한다는것을 의미한다.
- 이런 업데이트 과정에서 우리는 이전까지 만들어왔던 최대 길이를 알아야한다. (hi를 left로 삼아야 하므로)
- 하지만 이는 앞에서 봤던 식에서 볼 수 있듯이 정보가 많이 필요하므로 다른 방식으로 접근해야한다.
- 우리가 구하고자 하는 최소화시키고자하는 값은 base 에서부터 left까지가는 max left 값이다.
- base를 증가시키는것은 그 값만큼 왼쪽으로 확장시키는 허용 값을 늘리는것과 같다.
- 따라서 base를 0부터 시작하여 max값까지 dp[0][base] 값을구해 이 값들중 최소값을 구하면
- 문제는 해결된다.
- max값은 최악의 경우를 생각해서 정할 수 있다.
- 생각할 수 있는 구간의 최소 길이의 최악의 값은 2000인데
- 길이가 2000 이면 이후 부턴 - + 를 잘 조절해서 그 구간 내부에 구간을 설정할 수 있기 때문이다.
- 그러므로 left 의 최대 값은 2000이되고 base의 max 는 그것의 절반인 1000이 된다.
#include <bits/stdc++.h>
using namespace std;
vector<int> A;
int dp[10002][2001];
int solve(int idx, int left)
{
if (left >= 2001)
return left;
int &ret = dp[idx][left];
if (ret > 0)
return ret;
if (idx == A.size())
return ret = left;
ret = solve(idx + 1, left + A[idx]);
if (left >= A[idx])
ret = min(ret, max(left, solve(idx + 1, left - A[idx])));
return ret;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
A.resize(n);
for (int i = 0; i < n; i++)
{
cin >> A[i];
}
int ret = INT_MAX;
for (int i = 0; i <= A.size(); i++)
memset(dp[i], -1, sizeof(dp[i]));
for (int b = 0; b <= 1000; b++)
{
ret = min(ret, solve(0, b));
}
cout << ret << "\n";
}
return 0;
}
- 풀이 (iterative)
( https://www.youtube.com/watch?v=JRuAgCCwi0M 의 코드를 보고 작성한 풀이)
- 답의 범위는 1~2000 이다.
- 그러므로 답이 나올 수 있는 공간은 2000 * A.size() 임을 알 수 있으며
- 이를 i = 0 부터 하나씩 업데이트 하여 위에서와 같이 idx 와 left로 dp를 구성하여
- 답이 될 수 있는모든 경우의 수를 구할 수 있는 충분한 크기이다.
- left + a[i] 와 left - a[i] 의 4가지 가능한 경우(확장과 유지)를 처리해주면 문제를 해결할 수 있다.
- 이때 부분문제를 해결하는데 idx +1 와 idx 만 사용하므로 슬라이딩 윈도를 활용하여 메모리 공간을 줄일 수 있다.
- 이렇게 문제를 해결할 경우 이전 까지 만든 길이를 전부 알고 있으므로 왼쪽으로의 확장은
- wnd[cur][left] + a[i] - left 가 확장된 길이가 되고 left = 0 일때와 비교하여 업데이트 시켜주면 된다.
int solve()
{
int wnd[2][2001];
int nxt = 1;
int cur = 0;
fill(&wnd[cur][0], &wnd[cur][0] + 2001, INF);
wnd[cur][0] = 0;
for (int i = 0; i < a.size(); i++)
{
fill(&wnd[nxt][0], &wnd[nxt][0] + 2001, INF);
for (int left = 0; left < 2001; left++)
{
if (wnd[cur][left] == INF)
{
continue;
}
// plus
if (left + a[i] < 2001)
{
int update = 0;
// 범위 안
if (left + a[i] < wnd[cur][left])
{
update = wnd[cur][left];
}
// 범위 밖 -> 확장 가능성
else
{
update = left + a[i];
}
wnd[nxt][left + a[i]] = min(wnd[nxt][left + a[i]], update);
}
// minus
// 범위 안
if (left - a[i] >= 0)
{
wnd[nxt][left - a[i]] = min(wnd[nxt][left - a[i]], wnd[cur][left]);
}
// 범위 밖 -> 확장가능성 -> 맨 왼쪽에 오게되니 0 (base 업데이트)
else
{
wnd[nxt][0] = min(wnd[nxt][0], wnd[cur][left] + a[i] - left);
}
}
nxt = (nxt + 1) % 2;
cur = (cur + 1) % 2;
}
return *min_element(&wnd[cur][0], &wnd[cur][0] + 2001);
}
- 풀이 (bisearch)
- lo = 1, hi = 2000 으로 설정하고
- mid 값을 구하여 mid값이 길이가 될 수 있는지 체크하는 풀이방법.
'알고리즘 > codeforce' 카테고리의 다른 글
[codeforces] Codeforces Round #748 (Div. 3) A, C (0) | 2021.10.14 |
---|---|
[codeforces] Educational Codeforces Round 115 (Rated for Div. 2) A,B,C (0) | 2021.10.11 |