알고리즘 문제 풀이2

알고리즘 문제 풀이

4월에 푼 재미있는 문제들의 풀이를 작성해보았습니다.

문자열 장식

N개의 문자열이 주어지면 이 문자열들을 합쳐서 만들수 있는 사전순으로 가장 앞서는 문자열을 구하는 문제입니다. 단, 각 문자열 안에서의 상대적인 순서는 유지해야합니다.

우선 상대적인 순서를 유지해야 하니까 주어진 문자열들의 앞글자부터 하나씩 때어 온다고 생각합시다.

그러면, 매순간 각 문자열의 앞글자들 중에 사전순으로 가장 작은 알파벳이 있다면 그것을 때어 오는 것이 이득이라는 것을 쉽게 알 수 있습니다.

그런데 이러한 문자열이 여러개가 있으면 어떤 문자열에서 때어오는 것이 이득일까요?

이러한 문자열들의 뒷부분을 쭉 비교해나가면서 처음으로 다른 것이 나타나는 위치를 찾아봅시다. 이러한 위치에서 사전순으로 가장 작은 알파벳 $x$가 있다면 이 알파벳이 속한 문자열의 맨 앞을 때어 오는 것이 이득입니다.

왜냐하면, 다른 문자열에서 때어왔을 때 사전순으로 가장 작은 문자열을 만들었다고 가정하면, $x$가 속한 문자열의 맨 앞을 때어온 뒤, 이 문자열과 다른 문자열의 공통 부분을 같은 방식으로 소비하므로써 사전순으로 같거나 더 좋은 문자열을 항상 만들 수 있기 때문입니다.

이러한 $x$ 또한 여러개가 등장한다면, 어떻게 해야할까요? 마찬가지로 그 뒤의 문자열을 계속해서 비교해 나가면 됩니다. 이 과정을 반복하다보면 결국 남아 있는 문자열이 사전순으로 가장 작은 문자열의 맨 앞을 때어오는 것이 이득이라는 것과 같다는 것을 알 수 있습니다. 다만 위에서 $x$를 택한 것이 더 이득이라는 논리를 만족시키기 위해서는 $null$ 문자의 우선순위를 가장 크게 해주어야합니다. (빈칸이 알파벳보다 우선 순위가 높다는 뜻)

따라서 아래와 같은 코드로 해결할 수 있습니다. 시간 복잡도는 $O(N * MAXLEN^2)$ 입니다.

#include<bits/stdc++.h>
using namespace std;

int N;
string S[22];

int main() {
    std::ios::sync_with_stdio(false);

    cin >> N;

    int sum = 0;
    for(int i = 0; i < N; i++) {
        cin >> S[i];
        sum += S[i].size();
        S[i] += 'a';
    }

    for(int i = 0; i < sum; i++) {
        int a = min_element(S, S + N) - S;
        cout << S[a][0];
        S[a].erase(S[a].begin());
    }
}

P-수열

서로 다른수로 이루어진 수열의 모든 permutation 중 인접한 원소의 차이가 P로 나누어 떨어지지 않으면 P-수열이라고 할 때, P-수열의 개수를 묻는 문제입니다.

즉, P로 나눈 나머지가 같은 두 수가 인접해 있지 않은 permutation의 개수를 구하는 것입니다.

P로 나눈 나머지가 같은 두 수가 인접해 있다면, 그 둘 사이에 간선이 생긴다고 표현해보겠습니다.

그렇다면, 구하고자 하는 값은 ‘간선이 0개인 경우의 수’ 이고, 이는 포함과 배제의 법칙을 통해 아래와 같이 구할 수 있습니다.

(전체 경우의 수) - (특정 간선 1개가 있는 경우의 수) + (특정 간선 2개가 있는 경우의 수) - (특정 간선 3개가 있는 경우의 수) + …

따라서 우선 나머지가 같은 수들끼리 그룹을 나눈 다음 다음과 같은 dynamic programming 을 사용하여 해결할 수 있습니다.

dp1(x, n) := x번째 그룹~마지막 그룹까지 포함될 간선을 특정해 줄 것이고, x번째 이전 그룹들에서 만들어진 컴포넌트의 개수가 n개일 때, 위의 포함과 배제의 식에 더해지는 항의 합

transition 유용하게 계산하기 위하여 아래와 같은 dynamic programming 의 도움을 받을 수 있습니다.

dp2(n, m) := n개의 서로다른 공을 m개의 그룹으로 나누는 경우의 수. 단, 각 그룹 내에서의 순서를 고려해야한다.

위의 두 dynamic programming 을 떠올렸다면, 아래의 코드와 같은 방식으로 풀 수 있습니다. 시간 복잡도는 $O(N^3)$ 입니다.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod = 1234567891;

int exp(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}
int inv(int x) {
    return exp(x, mod - 2);
}
int fact[33], invf[33];

int N, P;
int cnt[1010];
vector<int> V;

ll cc2[33][33];
ll dp2(int n, int m) {
    ll &ret = cc2[n][m];
    if(ret != -1) return ret;
    if(n == 0) return ret = m == 0;

    ret = 0;
    if(m) {
        ret += 1LL * n * dp2(n - 1, m - 1) % mod;
        ret %= mod;
    }
    ret += 1LL * n * dp2(n - 1, m) % mod;
    ret %= mod;
    return ret;
}

ll cc1[33][33];
ll dp1(int x, int n) {
    if(x == V.size()) return (N - n) % 2? mod - fact[n] : fact[n];
    ll &ret = cc1[x][n];
    if(ret != -1) return ret;

    ret = 0;
    for(int i = 1; i <= V[x]; i++) {
        ret += 1LL * V[x] * dp2(V[x] - 1, i - 1) % mod * invf[i] % mod * dp1(x + 1, n + i) % mod;
        ret %= mod;
    }
    return ret;
}

void main2() {
    scanf("%d %d", &N, &P);

    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < N; i++) {
        int t; scanf("%d", &t);
        t = (t % P + P) % P;
        cnt[t]++;
    }
    V.clear();
    for(int i = 0; i < P; i++) if(cnt[i]) V.push_back(cnt[i]);

    memset(cc1, -1, sizeof(cc1));
    printf("%lld\n", dp1(0, 0));
}

int main() {
    fact[0] = 1;
    for(int i = 1; i < 33; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    for(int i = 0; i < 33; i++) {
        invf[i] = inv(fact[i]);
    }
    memset(cc2, -1, sizeof(cc2));
    for(int i = 0; i < 2; i++) main2();
}

알고리즘 문제 풀이2

알고리즘 문제 풀이

문자열 장식

P-수열

특별한 정렬 알고리즘들 2

트리의 종류와 이해