알고리즘 문제 풀이
알고리즘 문제 풀이
3월에 푼 재미있는 문제들의 풀이를 써보았습니다.
BOJ 1352번 문자열
아래와 같은 $dp$를 정의합니다.
$dp(x, sum)$ := $0$~$x-1$번째 인덱스까지 처음으로 사용한 문자들의 인덱스합이 $sum$ 일 때, $x$번째 ~ 마지막까지를 적절히 정하여 길이 $N$의 ideal string 을 만들수 있는지 여부(가능하면 1, 불가능하면 0) 이 $dp$의 transition은 어떻게 될까요? 각 상태에서 선택할 수 있는 것이 무엇인지 고민해 봅시다. 각 상태에서 우리가 정해야 하는 것은 $x$번째 인덱스에 들어올 문자입니다.
우리가 이 $dp$에서 알고자 하는 것은 최종적으로 ideal string을 만들수 있는가의 여부이기 때문에 $x$번째 인덱스에 들어올 문자를 구체적이게 정할 필요가 없고, 다음의 두가지로 분류하기만 하면 됩니다.
1) 이전에 나온 문자인가 2) 이전에 나온적이 없는 문자인가
1번의 경우, $dp(x, sum)$ 은 $dp(x + 1, sum)$ 문제로 transition 됩니다. 2번의 경우, $dp(x, sum)$ 은 $dp(x + 1, sum + x + 1)$ 문제로 transition 됩니다. (저는 0-based index 를 사용하여서 x + 1을 더했습니다.) 따라서, $dp(x, sum) = dp(x + 1, sum) | dp(x + 1, sum + x + 1)$ 입니다.
하지만, 여기서 끝이 아닙니다. 1번의 경우 이전에 나온 문자를 사용하려면 이전에 나온 문자중에 아직도 사용할 수 있는 문자가 남아있는 것이 있어야 합니다. 이것은 어떻게 판단할까요? 잘 생각해 보면 $sum$이 처음나온 문자들의 사용횟수 제한의 합입니다. 따라서 지금까지 사용한 문자수(=$x$) 가 $sum$보다 작으면 1번의 transition을 적용할 수 있습니다. 또한, 2번의 경우, $sum + x + 1$ 이 $N$을 넘어가는 것은 우리의 목적과 맞지 않습니다. 따라서 $sum + x + 1$ 이 $N$보다 작을 때만 transition 해줌으로서 $dp$의 상태를 $N^2$ 가지로 제한하여 줄수 있습니다.
모든 상태가 $N^2$ 가지이고 각 상태에서 transition 의 개수가 $O(1)$ 가지이므로 우리는 dp table을 $O(N^2)$ 시간에 채울 수 있습니다.
우선 이 $dp$를 사용하면 답이 존재하는지 존재하지 않는지는 알 수 있겠네요. 그러면 이제 그중 사전순으로 가장 앞에 있는 것을 구해봅시다!
우선 최적해의 모양을 떠올려 봅시다. 자명하게 다음과 같은 사실을 알 수 있습니다.
처음쓰는 문자들을 순서대로 모아보면, 알파벳 순이다. 즉, 처음쓰는 문자들을 쓰인 순서대로 놓으면, ABCD… 이런식으로 생겼을 것이라는 뜻입니다.
이 사실을 바탕으로 $dp$의 해복원을 하는 과정을 생각해 봅시다. 현재 $x$번째 인덱스의 문자를 결정할 차례라고 생각해봅시다.
두가지 경우가 있습니다.
1) $x$번째 인덱스에 이전에 사용했던 문자를 사용할 수 있다. 2) 그 외
위의 최적해를 관찰한 결과를 잘 생각해 보면 1번의 경우 새로운 문자를 추가하는 방법보다 이전에 사용했던 문자중에 남아있는 것을 사용하는 것이 이득입니다. 따라서 1번은 고민할 필요도 없이 이전에 사용한 문자들중에서 남은것 중에서 제일 사전순으로 앞서는 것을 채택하면 됩니다. 2번의 경우 어쩔수 없이 새로운 문자를 채택해야 겠네요. 지금까지 사용하지 않은 문자중에 사전순으로 가장 앞서는 것을 채택하여 줍니다. 지금까지 해가 존재하는 방향으로만 진행해 왔으니 2번의 경우 새로운 문자를 채택하는 것은 무조건 가능하겠네요.
이런식으로 그리디하게 복원을 해주면 됩니다!
아래는 이를 구현하는 코드입니다.
#include<bits/stdc++.h>
using namespace std;
int N;
int cc[111][111];
int dp(int x, int s) {
int &ret = cc[x][s];
if(ret != -1) return ret;
if(s == N && x == N) return ret = 1;
ret = 0;
if(x < s) ret |= dp(x + 1, s);
if(s + x + 1 <= N) ret |= dp(x + 1, s + x + 1);
return ret;
}
priority_queue<int> pq;
int cnt = 0;
void dfs(int x, int s) {
if(s == N && x == N) return;
if(x < s && dp(x + 1, s)) {
cout << (char)('A' - pq.top());
pq.pop();
dfs(x + 1, s);
}
else {
for(int i = 0; i < x; i++) pq.push(-cnt);
cout << (char)('A' + cnt++);
dfs(x + 1, s + x + 1);
}
}
int main() {
cin >> N;
memset(cc, -1, sizeof(cc));
if(dp(0, 0)) {
dfs(0, 0);
}
else printf("-1");
}
BOJ 2220 힙 정렬
잘 고민해보면 가장 작은 수인 1이 매 순간 힙의 가장 끝에 존재하게 만들면 최적임을 알 수 있습니다. 그렇게 하면 매순간 항상 맨 위에서 가장 깊은 곳까지 swap 이 일어날 것이기 때문입니다.
이러한 최적해가 존재한다고 가정했을 때 이 최적해를 구하는 방법을 제시해 보겠습니다.
우선 초기 힙상태의 각 노드에 순서대로 번호를 붙입니다.(실제 노드에 들어있을 값과는 다릅니다.) 그러면 매순간 pop을 할 때, 마지막 노드가 맨위로 가서 원하는 위치까지 swap 되는 과정을 simulation 합니다. 이 simulation에서 각 노드간의 대소관계가 규명이 됩니다. 이를 작은 쪽에서 큰 쪽으로 향하는 방향성 간선으로 표시해 줍니다.
이제 모든 simulation 을 마치면 초기 힙의 노드 번호에 대한 방향성 그래프가 완성됩니다. 우리는 이 방향성 그래프의 위상 정렬의 역순을 채택하면 답을 구할 수 있습니다.
이 최적해가 존재한다는 증명은 자세히 기술하진 않겠지만, 이런 과정으로 만들어진 방향성 그래프에 cycle이 없다는 사실을 보임으로써 증명할 수 있습니다.
또한 수학적 귀납법으로도 보일 수 있는데 이 과정에서 훨씬 간결한 풀이를 얻을 수 있습니다.
아래는 위상 정렬을 이용한 풀이의 코드입니다.
#include<bits/stdc++.h>
using namespace std;
const int MN = 100010;
int N;
int A[MN], vis[MN], ans[MN];
vector<int> adj[MN], ord;
void dfs(int u) {
vis[u] = 1;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if(vis[v]) continue;
dfs(v);
}
ord.push_back(u);
}
int main() {
cin >> N;
for(int i = 1; i <= N; i++) A[i] = i;
for(int i = 1; i <= N; i++) {
int l = 2 * i;
int r = 2 * i + 1;
if(l <= N) adj[l].push_back(i);
if(r <= N) adj[r].push_back(i);
}
for(int i = N; i >= 2; i--) {
vector<int> tmp;
int u = i - 1;
while(u != 1) {
int p = u / 2;
int v = u == 2 * p? 2 * p + 1 : 2 * p;
tmp.push_back(u);
adj[ A[i] ].push_back(A[u]);
if(v <= i - 1) {
adj[ A[v] ].push_back(A[u]);
adj[ A[i] ].push_back(A[v]);
}
u = p;
}
tmp.push_back(1);
for(int j = (int)tmp.size() - 1; j >= 1; j--) {
A[ tmp[j] ] = A[ tmp[j - 1] ];
}
A[ tmp[0] ] = A[i];
}
for(int i = 1; i <= N; i++) if(!vis[i]) {
dfs(i);
}
int cnt = N;
for(int i = 0; i < N; i++) ans[ ord[i] ] = cnt--;
for(int i = 1; i <= N; i++) {
printf("%d ", ans[i]);
}
}