딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/13392

#include <bits/stdc++.h>

#define MX 10003
using namespace std;

int N, dp[MX][11];
char A[MX], B[MX];


int dpf(int num, int left) {
    int &ret = dp[num][left];
    if (ret > 0) return ret;
    if (num == N) return 0;

    int lcnt = ((A[num] - B[num]) - left + 20) % 10;
    int rcnt = 10 - lcnt;

    return ret = min(dpf(num + 1, (left + lcnt) % 10) + lcnt, dpf(num + 1, left) + rcnt);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> B >> A;
    cout << dpf(0, 0) << '\n';
}

Prim과 Dijkstra는 모두 그리디 알고리즘 중 하나이다.

Prim은 최소 스패닝 트리를 구하는데 사용되고,

Dijkstra는 한 노드에서 모든 노드로 최단 경로를 구하는데 사용된다.

두 알고리즘은 상당히 유사한데

차이점으로는

Prim은 vertex 집합으로 부터 가까이 있는 노드를 선택하며 vertex 집합을 확장해 나가는 것이고,

Dikstra는 하나의 노드에서 가까이 있는 노드를 선택하며 vertex를 확장한다.

둘다 그리디하게 가까이 있는 노드로 퍼져나가며 최소 스패닝 트리를 구하거나, 최단 경로를 구하는 것이다.

두 알고리즘 모두 우선순위 큐를 사용하면 더 효율적인 알고리즘을 구성할 수 있는데,

연습삼아 우선순위 큐를 사용하지 않고 코드를 작성해봤다.

Prim

#include <bits/stdc++.h>

#define MX 1'000'003
using namespace std;

int W[5][5] = {
        {0, 1, 3, MX, MX},
        {1, 0, 3, 6, MX},
        {3, 3, 0, 4, 2},
        {MX, 6, 4, 0, 5},
        {MX, MX, 2, 5, 0}
};

vector<pair<int, int>> F;

void prim(int n) {
    int i, vnear, min;
    pair<int, int> e;
    int nearest[n + 1], distance[n + 1];

    F.clear();

    for (i = 2; i <= n; i++) {
        nearest[i] = 1;
        distance[i] = W[0][i-1];
    }

    for (int repeat = 1; repeat < n; repeat++) {
        //가장 가까운 vertex 뽑기
        min = MX;
        for (i = 2; i <= n; i++) {
            if (distance[i] >= 0 && distance[i] < min) {
                min = distance[i];
                vnear = i;
            }
        }
        e = {vnear, nearest[vnear]};
        F.push_back(e);
        distance[vnear] = -1;

        // 새로 추가된 vnear노드를 포함한 vertex 집합과 각 vertex 간의 거리 업데이트
        for (i = 2; i <= n; i++) {
            if (W[i-1][vnear-1] < distance[i]) {
                distance[i] = W[i-1][vnear-1];
                nearest[i] = vnear;
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    prim(5);

    for(auto a : F){
        cout << a.first << ' ' << a.second << '\n';
    }

}

Dijkstra

#include <bits/stdc++.h>

#define MX 1'000'003
using namespace std;

int W[5][5] = {
        {0, 7, 4, 6, 1},
        {MX, 0, MX, MX, MX},
        {MX, 2, 0, 5, MX},
        {MX, 3, MX, 0, MX},
        {MX, MX, MX, 1, 0}
};

vector<pair<int, int>> F;

void dijkstra(int n) {
    int i, vnear, min;
    pair<int, int> e;
    int touch[n + 1], length[n + 1];

    F.clear();

    for (i = 2; i <= n; i++) {
        touch[i] = 1;
        length[i] = W[0][i - 1];
    }

    for (int repeat = 1; repeat < n; repeat++) {
        //vertex 1번과 가장 가까운 vertex 뽑기
        min = MX;
        for (i = 2; i <= n; i++) {
            if (length[i] >= 0 && length[i] < min) {
                min = length[i];
                vnear = i;
            }
        }
        e = {vnear, touch[vnear]};
        F.push_back(e);

        // 새로 추가된 vnear노드를 경유하는 각 vertex 간의 거리 업데이트
        for (i = 2; i <= n; i++) {
            if (length[vnear] + W[vnear-1][i-1] < length[i]) {
                length[i] = length[vnear] + W[vnear-1][i-1];
                touch[i] = vnear;
            }
        }
        length[vnear] = -1;
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    dijkstra(5);

    for (auto a: F) {
        cout << a.first << ' ' << a.second << '\n';
    }

}

https://www.acmicpc.net/problem/12920

1. 문제설명

0-1 냅색알고리즘을 이용하는 문제이다.

이 문제에서는 아이템이 복수개인 경우가 존재한다.

이를 아이템 하나씩 나눠서 기존의 0-1 냅색 알고리즘을 시행하면 아이템 개수가 많아지기 때문에 시간초과가 난다.

아이템 개수 여러개를 줄여줄 수 있는 방법이 필요하다.

이진수는 모든 정수를 표현함을 이용하면 문제를 해결할 수 있다.

예를 들어 아이템 15개인 경우에는

아이템을 사용할 수 있는 경우의 수는

1, 2, 3, ... 15까지 총 15개가 있다.

이를 다른 방법으로 표현할 수 있다.

아이템을 하나씩 두는 게 아니라

아이템 1개, 아이템 2개, 아이템 4개, 아이템 8개로 덩어리를 만들어 새로운 아이템을 만들면

덩어리 4개로 15개를 표현할 수 있다.

이 문제에 적용하면 만약 무게 3, 만족도 4인 아이템의 개수 K가 10이라 치면

이를 다음과 같은 아이템으로 처리하고 0-1 냅색 알고리즘을 시행하면 된다.

일단 K가 10이므로 덩어리를 만들면

1, 2, 4, 3(2의 배수로 더이상 나눠지지 않으면 나머지는 그냥 둔다)으로 만들 수 있고

무게 3, 만족도 4,

무게 6, 만족도 8

무게 12, 만족도 16

무게 9, 만족도 12

인 아이템이 4개 있다고 생각하고 냅색 알고리즘을 시행하면

결과적으로 초기에 10개 있던 아이템에 대해서 아이템을 0개쓴경우부터 ~ 10개 다쓴경우가 적용되어

문제를 해결할 수 있다.

이렇게 하면 아이템의 총 개수가 log를 씌운 값에 가까워져서 연산을 덜 할 수 있다.

2.문제풀이코드 

#include <bits/stdc++.h>

using namespace std;

int N, M;
int dp[10001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        int V, C, K;
        cin >> V >> C >> K;

        int cnt = 1;
        while (K > 0) {
            cnt = min(cnt, K);
            for (int j = M; j >= V * cnt; j--) {
                dp[j] = max(dp[j], dp[j - V * cnt] + C * cnt);
            }
            K -= cnt;
            cnt *= 2;
        }
    }
    cout << dp[M] << '\n';

    return 0;
}

https://www.acmicpc.net/problem/13506

#include <bits/stdc++.h>

#define MX 1'000'003
using namespace std;

bool check[MX];
char s[MX];

vector<int> getFail() {
    int len = strlen(s);
    vector<int> fail(len);
    for (int j = 0, i = 1; i < len; i++) {
        while (j > 0 && s[i] != s[j]) j = fail[j - 1];
        if (s[i] == s[j]) fail[i] = ++j;
        if (i != len - 1) check[j] = 1;
    }
    return fail;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    vector<int> fail = getFail();
    int len = strlen(s);

    for(int i=fail[len-1]; i>0; i= fail[i-1]){
        if(check[i]){
            s[i] = 0;
            cout << s << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
    
    return 0;
}

https://www.acmicpc.net/problem/1893

#include <bits/stdc++.h>

using namespace std;

vector<int> getFail(const vector<int> &pattern) {
    int j = 0;
    vector<int> fail(pattern.size());
    for (int i = 1; i < pattern.size(); i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = fail[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            fail[i] = ++j;
        }
    }

    return fail;
}


bool KMP(const vector<int> &pattern, const vector<int> &text) {
    vector<int> fail = getFail(pattern);

    int cnt = 0;
    int j = 0;
    for (int i = 0; i < text.size(); i++) {
        while (j > 0 && pattern[j] != text[i]) {
            j = fail[j - 1];
        }

        if (pattern[j] == text[i]) {
            if (j == pattern.size() - 1) {
                cnt++;
                j = fail[j];
            } else {
                j++;
            }
        }
    }

    return cnt == 1;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    for (int t = 0; t < N; t++) {
        string A, W, S;
        cin >> A >> W >> S;

        vector<int> ans;

        map<char, int> charToInt;
        for (int i = 0; i < A.length(); i++) {
            charToInt[A[i]] = i;
        }

        int originPattern[W.length()];
        vector<int> text(S.length());

        //암호문 S를 숫자 배열로 변경
        for (int i = 0; i < S.length(); i++) {
            text[i] = charToInt[S[i]];
        }

        //W를 숫자 배열로 변경
        for (int i = 0; i < W.length(); i++) {
            originPattern[i] = charToInt[W[i]];
        }

        //W 모든 시프트 케이스 비교
        for (int i = 0; i < A.length(); i++) {
            vector<int> curPattern(W.length());

            for (int j = 0; j < W.length(); j++) {
                curPattern[j] = originPattern[j] + i;
                if (curPattern[j] >= A.length()) {
                    curPattern[j] -= A.length();
                }
            }


            //현재 패턴으로 케이스 비교
            if (KMP(curPattern, text)) {
                ans.push_back(i);
            }
        }

        //print
        if (ans.size() == 0) {
            cout << "no solution\n";
        } else if (ans.size() == 1) {
            cout << "unique: " << ans[0] << '\n';
        } else {
            cout << "ambiguous: ";
            for (auto a: ans) {
                cout << a << ' ';
            }
            cout << '\n';
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/21924

#include <bits/stdc++.h>

#define MX 100003
using namespace std;


int N, M;
int unf[MX];

int Find(int x) {
    if (unf[x] == -1) {
        return x;
    }
    return unf[x] = Find(unf[x]);
}

void merge(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a != b) {
        unf[a] = b;
    }
}

struct road {
    int a, b, c;

    bool operator<(const road &r) const {
        return c < r.c;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    fill(unf, unf + MX, -1);

    vector<road> v;
    long long total = 0;
    long long mst = 0;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({a, b, c});
        total += c;
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < M; i++) {
        auto [a, b, c] = v[i];

        a = Find(a);
        b = Find(b);
        if (a != b) {
            merge(a, b);
            mst += c;
        }
    }

    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        if (unf[i] == -1)cnt++;
    }

    if (cnt > 1) {
        cout << -1;
        return 0;
    }

    cout << total - mst << '\n';


    return 0;
}

https://www.acmicpc.net/problem/7575

#include <bits/stdc++.h>

using namespace std;

vector<int> getFail(const vector<int> &pattern) {
    int n = pattern.size();
    vector<int> fail(n);
    int j = 0;
    for (int i = 1; i < n; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = fail[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            fail[i] = ++j;
        }
    }
    return fail;
}

bool KMP(const vector<int> &pattern, const vector<int> &text) {
    vector<int> fail = getFail(pattern);
    int n = text.size();

    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = fail[j - 1];
        }
        if (text[i] == pattern[j]) {
            if (j == pattern.size() - 1) {
                return true;
            } else {
                j++;
            }
        }
    }

    return false;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> code[n];
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        vector<int> v(m);
        for (int j = 0; j < m; j++) {
            cin >> v[j];
        }
        code[i] = v;
    }

    // pattern
    for (int i = 0; i < code[0].size() - k + 1; i++) {
        vector<int> pattern(k);
        for (int j = 0; j < k; j++) {
            pattern[j] = code[0][i + j];
        }

        vector<bool> check(n);
        for (int j = 1; j < n; j++) {
            check[j] = KMP(pattern, code[j]);
        }

        // reverse
        for (int j = 1; j < n; j++) {
            if (check[j]) continue;
            reverse(code[j].begin(), code[j].end());
            check[j] = KMP(pattern, code[j]);
        }

        bool ans = true;

        for (int j = 1; j < n; j++) {
            if (!check[j]) {
                ans = false;
                break;
            }
        }

        if (ans) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";

    return 0;
}

https://www.acmicpc.net/problem/13711

1. 문제설명

1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때, 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.

이 문제는 두 수열의 LCS 크기를 구하는 문제이다.

단 조건으로 두 수열은 모두 1부터 N 사이의 숫자로 이루어져 있음을 준다.

문제에서 주어진 N이 10만이므로 O(N^2) 알고리즘인 LCS 알고리즘을 이용하면

시간초과로 틀린다.

문제에서 주어진 조건 두 수열은 모두 1부터 N 사이의 숫자로 이루어져있음을 활용하면

이 문제를 LIS 알고리즘으로 해결할 수 있다.

LIS는 수열이 주어졌을 때 수열 내 가장 긴 증가하는 부분을 구하는 알고리즘이다.

LIS 알고리즘은 이진탐색을 활용하면 O(NlogN)의 시간복잡도로 문제를 해결할 수 있다.

단 이 문제를 LIS로 해결하는 것을 생각해내기가 조금 어렵다.

예를 들어 두 수열 A, B가 다음과 같다고 가정하자

A : 4 5 6 1 2 3

B : 3 5 1 6 2 4

이 경우에 LCS 알고리즘으로 테이블을 그리면 답은 다음과 같다.

정답은 여러가지가 존재할 수 있지만

LCS의 길이는 3이 나온다.

A와 B는 둘다 1부터 N의 숫자로 이루어져있다.

LCS는 공통 부분 문자열을 구하는 것이므로

A와 B의 숫자를 같은 것 끼리 동일하게 변환을 해도 동일하게 공통 부분 문자열을 구할 수 있다.

좀 더 쉽게 예시를 들면

A : 4 5 6 1 2 3

B : 3 5 1 6 2 4

를

다음과 같이 변환해도 동일한 길이의 공통 부분 문자열을 바꿀 수 있다.

A,B에서 같은 원소를 동일하게 변환했기 때문이다.

위와 아래는 숫자는 다르지만 LCS의 길이를 구하는 데 있어서 동일한 상태라 볼 수 있다.

A : 1 2 3 4 5 6

B : 6 2 4 3 5 1

4->1

5->2

6->3

1->4

2->5

3->6

(A에 존재한 원소를 기준으로 변환한 것이다.)

이렇게 되면 이제 B에서 LIS를 구해주면 

LIS중 하나로

6 2 4 3 5 1

가 나오게 되고 길이는 3이 된다.

즉 1부터 N까지의 범위를 갖는 두 수열의 LCS 길이를 구하기 위해

수열을 변환하고 LIS 길이를 구하면 답을 구할 수 있다.

2. 문제풀이코드

#include <bits/stdc++.h>

#define MX 100003
using namespace std;

int n;
int A[MX], B[MX];
int changeNum[MX];
vector<int> ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> A[i];
    }
    for(int i=1; i<=n; i++){
        cin >> B[i];
    }

    //숫자 변환
    for(int i=1; i<=n; i++){
        changeNum[A[i]] = i;
    }
    for(int i=1; i<=n; i++){
        B[i] = changeNum[B[i]];
    }

    //Lis
    for(int i=1; i<=n; i++){
        int idx = lower_bound(ans.begin(), ans.end(), B[i]) - ans.begin();
        if(idx == ans.size()){
            ans.push_back(B[i]);
        }else{
            ans[idx] = B[i];
        }
    }

    cout << ans.size() << '\n';
    return 0;
}