면빈면빈면빈면빈

[적용한 알고리즘]

다익스트라

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

잠이 안와서 푸는 기본문항

<코드>

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

const int MAX_V = 20001;
const int INF = 1000000000;
typedef pair<int, int> P;

int main(){
    int V, E;
    vector<P> adj[MAX_V];
    scanf("%d %d", &V, &E);

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

    int dist[MAX_V];
    fill(dist, dist + MAX_V, INF);
    bool visited[MAX_V] = { 0 };
    priority_queue<P, vector<P>, greater<P>> PQ;

    dist[1] = 0;
    PQ.push(P(0, 1));

    while (!PQ.empty()){
        int cur;
        do {
            cur = PQ.top().second;
            PQ.pop();
        } while (!PQ.empty() && visited[cur]);

        if (visited[cur]) break;

        visited[cur] = true;
        for (auto &p : adj[cur]){
            int nxt_node = p.first;
            int nxt_cost = p.second;

            if (dist[nxt_node] > dist[cur] + nxt_cost){
                dist[nxt_node] = dist[cur] + nxt_cost;
                PQ.push(P(dist[nxt_node], nxt_node));
            }
        }
    }

    int ans_dist = -1;
    int ans_idx;
    int ans_cnt = 0;

    for (int i = V; i >= 1; i--){
        if (ans_dist < dist[i] && dist[i] != INF){
            ans_dist = dist[i];
            ans_idx = i;
            ans_cnt = 1;
        }
        else if (ans_dist == dist[i]){
            ans_idx = i;
            ans_cnt++;
        }
    }
    printf("%d %d %d\n", ans_idx, ans_dist, ans_cnt);

    return 0;
}

6549 번과 동일하다. 6549는 long 으로 바꿔야한다.

[적용한 알고리즘]

스택

[아이디어]

https://www.acmicpc.net/blog/view/12

에서 아이디어를 얻었다. 이해하는데 오래 걸렸던 것 같다. 빡대가리라..

결국 모든 높이를 살피되, 항상 현재 자신의 왼쪽만 살펴 시간 복잡도를 확 줄인 것이다. 

그걸 스택으로 구현한 것이고. 도대체 이런 생각을 어떻게 하는거지? 항상 벽을 느낀다.

[생각의 흐름 / 절차] 

[교훈]

분할정복으로도 풀 수 있고, 스택으로도 풀 수 있다고한다. 

원리를 제대로 이해하고 코드를 내 손으로 쓰기까지 더 연습해봐야겠다. 

<코드>

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
int H[100001];

int main(){
    int N; scanf("%d", &N);
    for (int i = 0; i < N; i++){
        scanf("%d", H + i);
    }

    stack<int> S;
    int ans = -1;

    for (int i = 0; i < N; i++){
        while (!S.empty() && H[S.top()] > H[i]){
            int height = H[S.top()];
            int width = i;
            S.pop();

            if (!S.empty()){
                width = (i - S.top() - 1);
            }

            ans = max(ans, width * height);
        }
        S.push(i);
    }

    while (!S.empty()){
        int height = H[S.top()];
        int width = N;
        S.pop();

        if (!S.empty()){
            width = N - S.top() - 1;
        }

        ans = max(ans, width * height);
    }

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

[적용한 알고리즘]

위상정렬

[아이디어]

위상정렬

[생각의 흐름 / 절차] 

[교훈]

기본 문제였다

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N = 1001;

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

    while (t--){
        int N, K;
        int indegree[MAX_N] = { 0 };
        int time[MAX_N] = { 0 };
        vector<int> adj[MAX_N];

        scanf("%d %d", &N, &K);

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

        for (int i = 0; i < K; i++){
            int from, to;
            scanf("%d %d", &from, &to);

            adj[from].push_back(to);
            indegree[to]++;
        }

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

        int result[MAX_N] = { 0 };
        queue<int> Q;

        for (int i = 1; i <= N; i++){
            if (indegree[i] == 0){
                result[i] = time[i];
                Q.push(i);
            }
        }

        for (int i = 1; i <= N; i++){
            int cur = Q.front();
            Q.pop();

            for (int nxt : adj[cur]){
                result[nxt] = max(result[nxt], result[cur] + time[nxt]);
                if (--indegree[nxt] == 0){
                    Q.push(nxt);
                }
            }
        }

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

[적용한 알고리즘]

위상정렬, 힙

[아이디어]

위상정렬 말고도 가장 작은 애를 큐에 담아야한다.

-> 우선순위 큐

[생각의 흐름 / 절차] 

지켜야할 규칙이

1. 위상정렬을 하여라

2. 가능한 가장 작은 애부터 뽑아라

1. 은 위상정렬을 통해 구현하면 된다.

2. 는 우선순위 큐(minHeap) 을 이용하면 되겠다. 

[교훈]

우선 순위 큐는 너무 강력한거 같다.

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N = 32001;

int main(){
    int N, M;
    int indegree[MAX_N] = { 0 };
    vector<int> adj[MAX_N];
    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; i++){
        int from, to;
        scanf("%d %d", &from, &to);

        indegree[to]++;
        adj[from].push_back(to);
    }

    int result[MAX_N] = { 0 };
    priority_queue<int, vector<int>, greater<int>> Q;

    for (int i = 1; i <= N; i++){
        if (indegree[i] == 0){
            Q.push(i);
        }
    }

    for (int i = 1; i <= N; i++){
        int cur = Q.top();
        Q.pop();
        result[i] = cur;

        for (int nxt : adj[cur]){
            if (--indegree[nxt] == 0){
                Q.push(nxt);
            }
        }
    }

    for (int i = 1; i <= N; i++){
        printf("%d ", result[i]);
    }

    return 0;
}

2252 줄 세우기 코드도 똑같다. 

종강했다. 할게 많지만 알고리즘은 재밌어서 계속하게되는 것 같다. 

[적용한 알고리즘]

위상정렬

[아이디어]

[생각의 흐름 / 절차] 

[교훈]

위상정렬의 기본 코드라고 한다.

언제나 kks 블로그에서 배운다. 없었으면 큰일 났을 것 같다. 

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 1002;

int main(){
    int N, M, indegree[MAX_V] = { 0 };
    vector<int> adj[MAX_V];
    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; i++){
        int K; scanf("%d", &K);
        if (K == 0) continue;
        int from, to;
        scanf("%d", &from);

        for (int j = 1; j < K; j++){
            scanf("%d", &to);
            adj[from].push_back(to);
            indegree[to]++;
            from = to;
        }
    }

    int result[MAX_V] = { 0 };
    queue<int> Q;

    for (int i = 1; i <= N; i++){
        if (indegree[i] == 0) Q.push(i);
    }

    for (int i = 1; i <= N; i++){
        if (Q.empty()){
            puts("0");
            return 0;
        }

        int cur = Q.front();
        result[i] = cur;
        Q.pop();

        for (int nxt : adj[cur]){
            if (--indegree[nxt] == 0) Q.push(nxt);
        }
    }

    for (int i = 1; i <= N; i++){
        printf("%d\n", result[i]);
    }

    return 0;
}

[적용한 알고리즘]

밸만포드

[아이디어]

[생각의 흐름 / 절차] 

내용

[교훈]

기본 문항이다. 음의 사이클을 어떻게 판단하는지 유심히 살펴보자.

참으로 유용한 블로그이다.

(http://kks227.blog.me/220796963742) 에서 배워감

<코드>

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#define MAX 501
using namespace std;
typedef pair<int, int> P;
const int INF = 1000000000;

int main(){
    int N, M, dist[MAX];
    scanf("%d %d", &N, &M);
    vector<P> adj[MAX];

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

    bool minusCycle = false;
    fill(dist, dist + N + 1, INF);
    dist[1] = 0;

    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            for (auto &p : adj[j]){ // j번에 연결된 애들
                int nxt = p.first;
                int nxt_cost = p.second;

                if (dist[j] != INF && dist[nxt] > dist[j] + nxt_cost){
                    dist[nxt] = dist[j] + nxt_cost;
                    if (i == N){
                        //맨 마지막에 루프를 한 번 더 돌아서 최단거리가 갱신되는지 확인을 해줘야함.
                        //음의 사이클이 존재하는지 판별가능.
                        minusCycle = true;
                    }
                }
            }
        }
    }

    if (minusCycle){
        printf("-1\n");
        return 0;
    }

    for (int i = 2; i <= N; i++){
        if (dist[i] == INF) printf("-1\n");
        else printf("%d\n", dist[i]);
    }

    return 0;
}

[적용한 알고리즘]

다익스트라

[아이디어]

목표지로 갈 때, 어차피 추가되는 성취감은 각 노드를 어떤 식으로 방문했든 h * E 로 일정하다.

그러므로, 가치가 최대가 되려면, 잃는 체력을 최소로 만들면 된다.

[생각의 흐름 / 절차] 

문제의 주인공이 하는 짓을 2개의 파트로 나눌 수 있다.

1. 목표지로 간다.

2. 고려대(부럽..)으로 간다. 

따라서, 2개의 절차로 나누어서 생각해볼 수 있다.

1. 1번 노드에서 X (2<= X <= N - 1) 번 노드로 가는 최소거리를 저장하는 dist 배열

2. N번 노드에서 X (2<= X <= N - 1)번 노드로 가는 최소거리를 저장하는 dist2 배열

을 다익스트라로 구해준 뒤, E * height[X] - (dist[X] + dist2[X]) * D 의 최댓값을 찾아주면 된다.

[교훈]

문항이 요구하는 조건을 정확하게 구현하는게 쉽지는 않았다. 

문제를 천천히 읽어보면서 다익스트라라는 감을 잡아야겠다.

그리고, 로직은 맞는거 같은데 계속 틀렸길래 자료형을 다 long long 으로 뜯어 고치고, 별 짓을 다했다.

코드가 복잡해 가독성이 많이 떨어지니 다시 깔끔하게 코드를 쓰고 업데이트를 해야겠다. (업데이트 완료)

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1000000000000
const int MAX_N = 100001;
using namespace std;
typedef pair<int, long long> P;
typedef long long int lld;
int N, M, D, E; //D: 체력 소모량, E: 성취감
int height[MAX_N];
vector<P> adj[MAX_N];

void dijkstra(int start_node, lld dist[]){
    priority_queue<P, vector<P>, greater<P>> PQ;
    bool visited[MAX_N] = { 0 };
    fill(dist, dist + N + 1, INF);
    dist[start_node] = 0;
    PQ.push(P(0, start_node));

    while (!PQ.empty()){
        int cur;
        do {
            cur = PQ.top().second;
            PQ.pop();
        } while (!PQ.empty() && visited[cur]);

        if (visited[cur]) break;
        visited[cur] = true;

        for (auto &p : adj[cur]){
            int nxt_node = p.first;
            int nxt_cost = p.second;

            if (height[nxt_node] > height[cur]){
                if (dist[nxt_node] > dist[cur] + nxt_cost){
                    dist[nxt_node] = dist[cur] + nxt_cost;
                    PQ.push(P(dist[nxt_node], nxt_node));
                }
            }
        }
    }
}
int main(){
    scanf("%d %d %d %d", &N, &M, &D, &E);
    for (int i = 1; i <= N; i++){
        scanf("%d", &height[i]);
    }

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

    lld dist1[MAX_N];
    lld dist2[MAX_N];

    dijkstra(1, dist1);
    dijkstra(N, dist2);

    lld ans = -INF;

    for (int i = 2; i <= N - 1; i++){
        if (dist1[i] == INF || dist2[i] == INF) continue;
        lld res = height[i] * E - (dist1[i] + dist2[i]) * D;
        ans = max(ans, res);
    }

    if (ans == -INF) printf("Impossible\n");
    else printf("%lld", ans);

    return 0;
}

[적용한 알고리즘]

다익스트라

[아이디어]

https://akim9905.tistory.com/45 와 똑같다. 벽이 cost가 되는거다.

[생각의 흐름 / 절차] 

내용

[교훈]

n, m으로 장난쳐놨다. 찾는데 한참 걸림. 조심들 하세요.

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAX = 101;
const int INF = 1000000000;

int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0 ,1, -1};
int n, m;
struct Ver{
    int x, y, dist;
    bool operator < (const Ver &v) const{
        return dist > v.dist;
    }
};

bool inMap(int x, int y){
    if (1 <= x && x <= n && 1 <= y && y <= m) return true;
    return false;
}

int main(){
    bool visited[MAX][MAX] = { 0 };
    int map[MAX][MAX] = { 0 };
    int dist[MAX][MAX] = { 0 };

    scanf("%d %d", &m, &n);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            scanf("%1d", &map[i][j]);
            dist[i][j] = INF;
        }
    }

    dist[1][1] = 0;
    priority_queue<Ver> PQ;
    PQ.push({1, 1, dist[1][1]});

    while (!PQ.empty()) {
        Ver cur;
        do {
            cur = PQ.top();
            PQ.pop();
        } while (!PQ.empty() && visited[cur.x][cur.y]);

        if (visited[cur.x][cur.y]) break;
        visited[cur.x][cur.y] = true;

        for (int k = 0; k < 4; k++) {
            int nx = cur.x + dirx[k];
            int ny = cur.y + diry[k];

            if (inMap(nx, ny)) {
                if (dist[nx][ny] > dist[cur.x][cur.y] + map[nx][ny]) {
                    dist[nx][ny] = dist[cur.x][cur.y] + map[nx][ny];
                    PQ.push({nx, ny, dist[nx][ny]});
                }
            }
        }
    }

    printf("%d", dist[n][m]);
    return 0;
}

[적용한 알고리즘]

다익스트라

[아이디어]

1~N까지 다익스트라를 실행해 X까지 가는 최소비용을 각각 구해준뒤 각 마을의 time 배열에 더해준다.

다만 X 일때는 각자의 마을로 돌아가는 것이므로, 이때는 X를 제외한 모두에게 최소비용을 더해준다.

[생각의 흐름 / 절차] 

내용

[교훈]

익숙해지는 중.

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int MAX_N = 1001;
const int INF = 1000000000;
int N, M, X;

int main(){
    scanf("%d %d %d", &N, &M, &X);
    vector<P> adj[MAX_N];

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

    int time[MAX_N] = { 0 };

    for (int i = 1; i <= N; i++){ //1~N 까지 다익스트라
        int dist[MAX_N]; fill(dist, dist + N + 1, INF);
        bool visited[MAX_N] = { 0 };
        priority_queue<P, vector<P>, greater<P>> PQ;

        dist[i] = 0;
        PQ.push(P(0, i));

        while (!PQ.empty()){
            int cur;

            do {
                cur = PQ.top().second; //현재 노드
                PQ.pop();
            } while (!PQ.empty() && visited[cur]);

            // 현재 X 노드에서 다익스트라를 쓰지 않고, 방문한 노드가 X라면 종료.
            // 이미 X에서 경로 cost 의 최솟값은 알 것이기 떄문에
            if (i != X && cur == X) break;
            if (visited[cur]) break;
            visited[cur] = true;

            for (auto &p : adj[cur]){
                int nxt_node = p.first;
                int nxt_cost = p.second;

                if (dist[nxt_node] > dist[cur] + nxt_cost){
                    dist[nxt_node] = dist[cur] + nxt_cost;
                    PQ.push(P(dist[nxt_node], nxt_node));
                }
            }
        }
        // X에서 시작한 다익스트라의 경우 X에서 각자 집으로 돌아가는 거기 때문에 경로 최솟값들을 다 더해줌.
        if (i == X){
            for (int k = 1; k <= N; k++){
                if (k == X) continue;
                time[k] += dist[k];
            }
        }
        // X에서 시작한게 아니라면, X까지의 dist 값을 알아내서 더해주면 됨.
        else {
            time[i] += dist[X];
        }
    }

    int ans = -1;
    for (int i = 1; i <= N; i++){
        ans = max(time[i], ans);
    }

    printf("%d\n", ans);

    return 0;
}

[적용한 알고리즘]

다익스트라 알고리즘

[아이디어]

다익스트라의 기본적인 문항이라고 한다.

다만 각 칸 자체가 cost 로 봐줘야한다.

[생각의 흐름 / 절차] 

내용

[교훈]

근데 저 알고리즘인지 몰랐다면, 아직 허접인 나는 이게 

DP 문제인 줄 알았을 것 같다. 어디서 차이를 알아야하는 거지?

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAX = 126;
const int INF = 1000000000;

int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0 ,1, -1};
int n;
struct Ver{
    int x, y, dist;
    bool operator < (const Ver &v) const{
        return dist > v.dist;
    }
};

bool inMap(int x, int y){
    if (1 <= x && x <= n && 1 <= y && y <= n) return true;
    return false;
}

int main(){
    int t = 0;
    while (true){
        t++;
        bool visited[MAX][MAX] = { 0 };
        int map[MAX][MAX] = { 0 };
        int dist[MAX][MAX] = { 0 };

        scanf("%d", &n);
        if (n == 0) return 0;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                scanf("%d", &map[i][j]);
                dist[i][j] = INF;
            }
        }

        dist[1][1] = map[1][1];
        priority_queue<Ver> PQ;
        PQ.push({1, 1, dist[1][1]});

        while (!PQ.empty()){
            Ver cur;

            do {
                cur = PQ.top();
                PQ.pop();
            } while (!PQ.empty() && visited[cur.x][cur.y]);

            if (visited[cur.x][cur.y]) break;
            visited[cur.x][cur.y] = true;

            for (int k = 0; k < 4; k++){
                int nx = cur.x + dirx[k];
                int ny = cur.y + diry[k];

                if (inMap(nx, ny) && !visited[nx][ny]){
                    if (dist[nx][ny] > dist[cur.x][cur.y] + map[nx][ny]){
                        dist[nx][ny] = dist[cur.x][cur.y] + map[nx][ny];
                        PQ.push({nx, ny, dist[nx][ny]});
                    }
                }
            }
        }
        printf("Problem %d: %d\n", t, dist[n][n]);
    }
}