면빈면빈면빈면빈

[적용한 알고리즘]

DP

[아이디어]

요즘은 dp를 재귀로 풀려고 노력 중이다. 

재귀에 약했는데 익숙해져보니 재귀가 더 직관적인 거 같기도 하다. 

초반에 등차수열을 이루는 숫자들을 알아서 배열시키면 되므로,

배열을 우선 정렬시키는 것이 자연스러운 생각이다.

go(i, j) : a[j] - a[i] 를 공차로 가지는 수열의 최대 길이로 하자.

a[j] - a[i] = d 라고하면, 

a[k] = a[j] + d 를 만족시키는 k 가 존재한다면,

cache[i][j] = cache[j][k] + 1 이다. 

근데 문제는 k 를 찾는 방법이다. 

1. 그냥 전수조사 : (i, j) 쌍을 모조리 다 검색하는데 시간 복잡도 N^2, 전수조사에 N 이므로 시간 복잡도는 N^3 이라 TLE 난다.

2. 데이터를 정렬시켜 놨으므로, 어디있는 지 찾을 수 있는 아주 좋은 lower_bound 함수를 이용하자.

이분 탐색에 걸리는 시간 복잡도가 log N 이므로, 전체 시간 복잡도는 O(N^2logN) 으로 십가능이다.

그리고, 예외적으로 공차가 0인 것들은 처리가 안되므로,

미리 처리해준다. (이거 때문에 오지게 틀렸다.)

[교훈]

쉽지 않다. dp는

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 2001;
int N;
int cache[MAX][MAX];
vector<int> num;

int go(int i, int j){
    if (i > j) return 0;
    else if (i == j) return 1;

    int &ret = cache[i][j];
    if (ret != -1) return ret;
    ret = 2;

    int d = num[j] - num[i];
    int nxt = num[j] + d;

    int idx = lower_bound(num.begin(), num.end(), nxt) - num.begin();

    if (num[idx] == nxt) return ret = go(j, idx) + 1;
    return ret;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(cache, -1, sizeof(cache));

    cin >> N;
    for (int i = 0; i < N; i++){
        int x;
        cin >> x;
        num.push_back(x);
    }
    sort(num.begin(), num.end());

    int ans = 1;
    int cnt = 1;
    for (int i = 1; i <= N; i++){
        if (num[i] == num[i - 1]){
            ans = max(ans, ++cnt);
        }
        else cnt = 1;
    }

    num.erase(unique(num.begin(), num.end()), num.end());
    //같은 수들 지워줌
    
    int N = num.size();
    for (int i = 0; i < N - 1; i++){
        for (int j = i + 1; j < N; j++){
            ans = max(ans, go(i, j));
        }
    }

    cout << ans << endl;
    return 0;
}

[적용한 알고리즘]

(굳이 꼽자면) 그래프, 행렬

[아이디어]

요약하면, A->B 까지 정확히 K번 거쳐서 갈 수 있느냐는 말이다.

행렬의 거듭제곱을 이용하면 구할 수 있다고 한다.

"행렬 A^k 에서 (i, j) 의 의미가 결국  i->j 까지 k 번만에 갈 수 있느냐?" 이므로,

행렬 거듭제곱 알고리즘만 짜면 된다.

[교훈]

내용

<코드>

#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<bool>> matrix;

matrix operator * (const matrix &a, const matrix &b){
    int n = a.size();
    matrix c(n, vector<bool>(n));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 0; k < n; k++){
                if (a[i][k] & b[k][j]){
                    c[i][j] = true;
                }
            }
        }
    }

    return c;
}

matrix pow(matrix a, int M){
    int N = a.size();
    matrix ans(N, vector<bool>(N));

    for (int i = 0; i < N; i++) ans[i][i] = true;

    while (M > 0){
        if (M % 2 == 1){
            ans = ans * a;
        }
        a = a * a;
        M /= 2;
    }
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K, M;
    cin >> N >> K >> M;
    matrix Game(N, vector<bool>(N));

    for (int i = 0; i < N; i++){
        int x, y;
        cin >> x >> y;
        Game[i][x - 1] = true;
        Game[i][y - 1] = true;
    }

    matrix ans = pow(Game, K);

    while (M--){
        int x, y;
        cin >> x >> y;

        printf("%s\n", ans[x - 1][y - 1] ? "death" : "life");
    }
    return 0;
}

[적용한 알고리즘]

MST(크루스칼)

[아이디어]

하고 싶은게 두 가지다.

1. 두 마을로 쪼개고 싶다. (최소한의 경로만 남겨놓고)

2. 유지비를 최소로 하고 싶다. 

MST 를 만들어야할 것 같은데, 두 마을로 어떻게 쪼갤 지 고민을 하다보면,

우선 MST 를 만든 뒤, 만든 간선 중 가장 값이 큰 간선 하나를 제외시켜버리면 된다.

근데 크루스칼 알고리즘에서는 값이 가장 큰 간선이 가장 마지막에 추가되므로,

마지막 반복문을 안돌리면 되는 거다.

[교훈]

그래프..

<코드>

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct Edge {
    int start, end, cost;
    bool operator < (const Edge &other) const {
        return cost < other.cost;
    }
};

int Parent[100001];

int Find(int x){
    if (x == Parent[x]){
        return x;
    }
    return Parent[x] = Find(Parent[x]);
}

bool Merge(int x, int y){
    x = Find(x);
    y = Find(y);

    if (x == y) return false;
    Parent[x] = y;
    return true;
}

int main(){
    int N, M;
    scanf("%d %d", &N, &M);

    for (int i = 1; i <= N; i++){
        Parent[i] = i;
    }

    vector<Edge> E;
    for (int i = 0; i < M; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        E.push_back({from, to, cost});
    }

    sort(E.begin(), E.end());
    int ans = 0;
    int cnt = 0;

    for (int i = 0; i < M; i++){
        Edge cur = E[i];

        if (Merge(cur.start, cur.end)){
            ans += cur.cost;
            cnt++;
        }

        if (cnt == N - 2){
            break;
        }
    }

    printf("%d\n", ans);
    return 0;
}

[적용한 알고리즘]

플로이드-와샬

[아이디어]

x->y 로 가는 경로가 있는가?

y->x 로 가는 경로가 있는가?

둘 다 없는가? 

를 알아보면 되겠다.

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 401;

bool dist[MAX_N][MAX_N];
int main(){
    int N, K;
    scanf("%d %d", &N, &K);

    for (int i = 0; i < K; i++){
        int first, second;
        scanf("%d %d", &first, &second);
        dist[first][second] = true;
    }

    for (int k = 1; k <= N; k++){
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                if (dist[i][k] && dist[k][j]){
                    dist[i][j] = true;
                }
            }
        }
    }

    int Q;
    scanf("%d", &Q);

    while (Q--){
        int x, y;
        scanf("%d %d", &x, &y);
        if (dist[x][y]) printf("-1\n");
        else if (dist[y][x]) printf("1\n");
        else printf("0\n");
    }
    return 0;
}

[적용한 알고리즘]

다익스트라

[아이디어]

dist 배열을 최단경로를 저장하는 곳이 아닌,

k 개의 '최단경로들' 을 저장하는 용도로 사용한다.

(Heap 을 이용해서)

따라서 dist[i].top() 은 출발점에서 i 로 가는 k 번째 최단경로이다.

그래서 기존의 다익스트라에서 최단경로를 저장하는 부분을 살짝 손봐줘야하는데,

dist[nxt].size() < K 이거나 dist[nxt].top() > (현재 정점까지 k 번째 최단경로) + cost 라면,

dist[nxt] 에 ((현재 정점까지 k 번째 최단경로) + cost) push,

원래의 우선순위 큐에는 {(현재 정점까지 k 번째 최단경로) + cost, 다음 정점) 을 push 해주면 되겠다.

그리고 만약 size() 가 k 였다면, 하나를 당연히 pop 해줘야한다.

끝까지 돌았을 때 경로의 수가 k 개가 안된다면, 그 경로가 없는 것이므로 -1

있다면 top 을 출력하면 된다.

[교훈]

개 어 렵..

<코드>

#include <cstdio>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int MAX_V = 10001;
int N, M, K;

int main(){
    scanf("%d %d %d", &N, &M, &K);
    vector<pair<int, int>> adj[MAX_V];

    for (int i = 0; i < M; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        adj[from].push_back({to, cost});
    }

    priority_queue<int> dist[MAX_V];
    priority_queue<P, vector<P>, greater<P>> PQ;
    dist[1].push(0);
    PQ.push({0, 1});

    while (!PQ.empty()){
        auto p = PQ.top();
        PQ.pop();

        int cur = p.second;
        int dist_cur = p.first;
        
        for (auto q : adj[cur]){
            int nxt = q.first;
            int cost = q.second;

            if (dist[nxt].size() < K || dist[nxt].top() > dist_cur + cost){
                if (dist[nxt].size() == K){
                    dist[nxt].pop();
                }
                dist[nxt].push(dist_cur + cost);
                PQ.push({dist_cur + cost, nxt});
            }
        }
    }

    for (int i = 1; i <= N; i++){
        if (dist[i].size() != K){
            printf("-1\n");
        }
        else {
            printf("%d\n", dist[i].top());
        }
    }
    return 0;
}

[적용한 알고리즘]

플로이드 와샬

[아이디어]

i -> j 로 가는 경로가 있다고 가정해보자.

이때, i -> k -> j 가 가능하다면, i -> j 는 선택하면 안된다.

구하는 값이 간선의 개수를 최소화하는 것이기 때문이다.

따라서, 플로이드-와샬을 이용해서

dist[i][j] = dist[i][k] + dist[k][j] 를 만족하는 k 가 존재한다면,

그 간선을 사용하지 않으면 된다.

<코드>

#include <cstdio>
using namespace std;

int dist[21][21];
bool notUse[21][21];

int main(){
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            scanf("%d", &dist[i][j]);
        }
    }

    for (int k = 1; k <= N; k++){
        for (int i = 1; i <= N; i++){
            if (i == k) continue;
            for (int j = 1; j <= N; j++){
                if (i == j) continue;
                if (k == j) continue;

                if (dist[i][j] == dist[i][k] + dist[k][j]){
                    notUse[i][j] = true;
                }

                if (dist[i][j] > dist[i][k] + dist[k][j]){
                    printf("-1\n");
                    return 0;
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            if (notUse[i][j]) continue;
            ans += dist[i][j];
        }
    }

    printf("%d\n", ans / 2);
    return 0;
}

[적용한 알고리즘]

그래프, 플로이드-와샬

[아이디어]

플로이드는 음의 간선이 없는 사이클을 도는 것까지

dist[i][i] (i = 1~N) 까지 나타내므로..

[교훈]

플로이드 와샬 알고리즘은 사이클까지 나타내준다..? 정도?

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_V = 401;
const int INF = 1000000000;

int V, E;
int Dist[MAX_V][MAX_V];
int main(){
    scanf("%d %d", &V, &E);
    for (int i = 0; i < E; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        Dist[from][to] = cost;
    }

    for (int i = 1; i <= V; i++){
        for (int j = 1; j <= V; j++){
            if (Dist[i][j] != 0) continue;
            Dist[i][j] = INF;
        }
    }

    for (int k = 1; k <= V; k++){
        for (int i = 1; i <= V; i++){
            for (int j = 1; j <= V; j++){
                Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]);
            }
        }
    }

    int ans = INF;
    for (int i = 1; i <= V; i++){
        ans = min(ans, Dist[i][i]);
    }

    printf("%d\n", ans == INF ? -1 : ans);
    return 0;
}

[적용한 알고리즘]

그래프, 플로이드

[아이디어]

1. 단방향, 양방향 간선이 섞인 그래프를 DAG 로 바꿀 수 있느냐? 가 문제다.

2. 결국 주어진 그래프에서 사이클이 없도록 그래프를 구성할 수 있느냐? 가 핵심이다.

3. 가능한 그래프의 종류를 국소적으로 살펴보면서 생각해보면,

 1) 단방향 간선으로 이루어진 사이클이 존재하는 경우 : 무조건 NO

 2) 양방향 간선으로 이루어진 사이클이 존재하는 경우 : 사이클은 무조건 DAG 로 바꿀 수 있음 (위상정렬)

 3) 단/양 섞인 사이클 : 이것 역시 가능

 4) 사이클이 없는 단방향 그래프 : 설명할 필요 없이 가능

따라서 곰곰이 생각하다보면 1) 만 걸러주면 되므로,

단방향 사이클이 존재하는지만 생각해보면 된다. 

[교훈]

문제 한참 어렵다가 아이디어 하나로 모든게 술술 풀릴 때 쾌감이란

블로그 업데이트를 한참 못했으니 밀린 것도 좀 업데이트 해야겠다.

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N = 101;
bool Dist[MAX_N][MAX_N];
char Path[MAX_N][MAX_N];

int main(){
    int N;
    scanf("%d", &N);

    for (int i = 1; i <= N; i++){
        scanf("%s", Path[i] + 1);
    }

    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
           Dist[i][j] = (Path[i][j] == 'Y' && Path[j][i] == 'N');
        }
    }

    for (int k = 1; k <= N; k++){
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                if (Dist[i][k] && Dist[k][j]){
                    Dist[i][j] = true;
                }
            }
        }
    }

    for (int i = 1; i <= N; i++){
        if (Dist[i][i]){
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}

[적용한 알고리즘]

MST(최소 신장 트리, 미니멈 스패닝 트리, 최소 스패닝 트리..)

[아이디어]

기본 문제라고 한다. 항상 그렇듯 출처는 kks 님의 블로그

[교훈]

Edge 를 정의한 방식이 싱기방기하다.

공부를 더해야겠다.

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;

int UF[1001];

int find(int a){
    if (UF[a] < 0) return a;
    return UF[a] = find(UF[a]);
}

bool merge(int a, int b){
    a = find(a);
    b = find(b);

    if (a == b) return false;
    UF[b] = a;
    return true;
}

struct Edge{
    int u, v, w;
    Edge(): Edge(-1, -1, 0){}
    Edge(int u1, int v1, int w1): u(u1), v(v1), w(w1){}
    bool operator < (const Edge& O) const {
        return w < O.w;
    }
};
int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    Edge e[100001];

    for (int i = 0; i < M; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        e[i] = Edge(a - 1, b - 1, c);
    }
    sort(e, e + M);

    int result = 0;
    int cnt = 0;
    fill(UF, UF + N, -1);
    for (int i = 0;; i++){
        if (merge(e[i].u, e[i].v)){
            result += e[i].w;
            if (++cnt == N - 1) break;
        }
    }

    printf("%d\n", result);
    return 0;
}

[적용한 알고리즘]

DP

[아이디어]

1번과 N번이 둘 다 색칠되는 경우를 제외하고는, 나머지 경우는 선형으로 생각해줘도 된다.

dp[N][K] = N 개 짜리 색상환을 중 K 개를 인접하지 않게 칠하는 경우의 수

두 가지 경우로 나눌 수 있는데,

현재 i 번째 칸을 보고 있고

j 개의 칸을 칠했다고 하면,

1. i 번째 칸을 칠하는 경우 = dp[i - 2][j - 1]

2. 안칠하는 경우 = dp[i - 1][j] 

이므로, dp[i][j] = dp[i - 2][j - 1] + dp[i - 1][j] 다

이때 문제가 되는게 dp[n][k] 인데,

dp[n][k] 면 

1. N번째 칸을 칠하는 경우

1 번 칸을 칠해서는 안되고, N - 1번 칸도 칠하면 안되므로,

2 ~ N - 1 까지의 칸을 K - 1개의 색을 인접하지 않게 칠하는 경우와 같으므로,

dp[N-3][K - 1] 개이다

2. N번째 칸을 칠하지 않는 경우

1 ~ N - 1 까지 K 개의 색을 인접하지 않게 칠하는 경우와 같으므로,

dp[N - 1][K] 이다

따라서, dp[N][K] = dp[N - 3][K - 1] + dp[N - 1][K] 으로 구할 수 있다.

[교훈]

오랜만에 재밌는 확통 문제 푼 느낌이다.

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;
const int mod = 1000000003;
int dp[1001][1001];
int N, K;

int main(){
    scanf("%d %d", &N, &K);
    for (int i = 0; i <= N; i++){
        dp[i][1] = i;
        dp[i][0] = 1;
    }

    for (int i = 2; i <= N; i++){
        for (int j = 2; j <= K; j++){
            dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % mod;
        }
    }

    int ans = (dp[N - 1][K] + dp[N - 3][K - 1]) % mod;
    printf("%d\n", ans);

    return 0;
}