딩코딩 : Computer Science 블로그

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

#include <bits/stdc++.h>

#define MX 101
using namespace std;


int N, K, ans, seq[22];
bool chk[22];
string arr[22];
char resArr[400];

int fail[200];

void getFail() {
    memset(fail, 0, sizeof(fail));
    int len = strlen(resArr);
    for (int j = 0, i = 1; i < len; i++) {
        while (j > 0 && resArr[i] != resArr[j]) {
            j = fail[j - 1];
        }
        if (resArr[i] == resArr[j]) {
            fail[i] = ++j;
        }
    }
}

int KMP() {
    int ans = 0;
    int len = strlen(resArr);
    for (int i = 0; i < len; i++) {
        resArr[i + len] = resArr[i];
    }

    int patternLen = len;
    len = strlen(resArr);
    for (int j = 0, i = 0; i < len - 1; i++) {
        while (j > 0 && resArr[j] != resArr[i]) {
            j = fail[j - 1];
        }
        if (resArr[i] == resArr[j]) {
            if (j == patternLen - 1) {
                ans++;
                j = fail[j];
            } else {
                j++;
            }

        }
    }


    return ans;
}


void makeSequence(int L) {
    if (L == N) {
        int idx = 0;
        memset(resArr, 0, sizeof(resArr));
        for (int i = 0; i < N; i++) {
            string curStr = arr[seq[i] - 1];
            int strLen = curStr.length();
            for (int j = 0; j < strLen; j++) {
                resArr[idx++] = curStr[j];
            }
        }
        getFail();
        if (KMP() == K) {
            ans++;
        }
        return;
    }

    for (int i = 1; i <= N; i++) {
        if (!chk[i]) {
            chk[i] = 1;
            seq[L] = i;
            makeSequence(L + 1);
            chk[i] = 0;
        }
    }

}


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

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    cin >> K;

    makeSequence(0);

    cout << ans << '\n';


    return 0;
}

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

#include <bits/stdc++.h>

#define MX 101
using namespace std;

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


int dpf(int now, int x, int y, int z) {
    if (now == N) return 0;
    int &ret = dp[now][x][y][z];
    if (ret != -1) return ret;

    ret = 1e9;

    //현재 다른 칸 수
    int df = (B[now] - x + 10) % 10;
    //돌려야 할 칸 수 왼쪽, 오른쪽
    int d[2] = {df, 10 - df};

    // x는 d[0] 이나 d[1]만큼 돌리고, y는 0~d[0] 0~d[1] 만큼 돌릴 수 있고, z는 0~j만큼 돌릴 수 있다.
    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= d[i]; j++) {
            for (int k = 0; k <= j; k++) {
                //x를 왼쪽으로 돌리는 경우와 오른쪽으로 돌리는 경우를 구분
                int yy = (y + (i ? -j : j) + 10) % 10;
                int zz = (z + (i ? -k : k) + 10) % 10;

                //전체 돌리는 횟수 계산
                int val = dpf(now + 1, yy, zz, A[now + 3]);
                val += ((d[i] - j + 2) / 3 + (j - k + 2) / 3 + (k + 2) / 3);
                ret = min(ret, val);
            }
        }
    }
    return ret;
}


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

    cin >> N >> AC >> BC;
    memset(dp, -1, sizeof(dp));

    for (int i = 0; i < N; i++) {
        A[i] = AC[i] - '0';
        B[i] = BC[i] - '0';
    }

    cout << dpf(0, A[0], A[1], A[2]) << '\n';
    return 0;
}

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;
}