글 읽기 - 메모리 초과 이유를 알고 싶습니다.

ohyeaha 2년 전 0

안녕하세요,

블로그를 참고하여 priority_queue를 이용해 구현했습니다. 그런데 60% 대에서 메모리 초과가 발생합니다.

메모리를 나름 효율적으로 쓰기위해 간선 vector를 local 변수로 정점 개수만큼 만들었는데..

아래 코드에서 어떤 부분이 문제가 될지 조언을 주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int INF = 1000000000;
int V, E, start;

struct MyLess {
    bool operator() (pair<int,int> a, pair<int,int> b) {
        return a.first > b.first;
    }
};

void dikstra(int start, int dp[], vector<pair<int, int>> arr[]) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, MyLess> pq;
    dp[start] = 0;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        auto temp = pq.top();
        pq.pop();
        if (dp[temp.second] < temp.first) continue;

        for (auto& itr : arr[temp.second]) {
            int next = itr.first;
            int nextDistance = temp.first + itr.second;
            dp[next] = min(dp[next], nextDistance);
            pq.push(make_pair(nextDistance, next));
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> V >> E;
    cin >> start;

    vector<pair<int, int>> arr[V+1];
    int u, v, w;
    for (int i = 0; i < E; i++) {
        cin >> u >> v >> w;
        arr[u].push_back(make_pair(v, w));
    }

    int dp[V+1];
    for (int i = 1; i <= V; i++) {
        dp[i] = INF;
    }
    dikstra(start, dp, arr);
    for (int i = 1; i <= V; i++) {
        dp[i] >= INF
                ? cout << "INF" << endl
                          : cout << dp[i] << endl;
    }

    return 0;
}

djm03178 2년 전 2

메모리의 제한은 주로 의도된 공간 복잡도라면 아무리 비효율적이더라도 매우 넉넉하게 통과될 수 있을 정도로 줍니다. 따라서 메모리 초과가 발생했다면 그건 거의 대부분 공간 복잡도 자체가 의도보다 커졌을 때입니다.

메모리의 효율성을 높이기 위해 입력에서 딱 사용하는 만큼만 메모리를 할당받는 것은 실제로는 효과가 거의 없고, 오히려 최대 크기의 고정 배열을 잡는 것보다 일반적으로 더 메모리를 많이 쓰게 될 뿐만 아니라 시간도 더 오래 걸립니다. 왜냐하면 문제 풀이에서 중요한 것은 평균적인 메모리 소모량이 아닌 최악의 경우에서의 메모리 사용량이고, 이는 일반적으로 최대 크기의 입력에 해당되기 때문에 최대 크기만큼 고정 배열을 잡는 것과 다를 것이 없기 때문입니다. 게다가 고정 배열은 딱 그만큼만 할당받고 그대로 접근할 수 있지만, vector 등을 사용하는 것은 동적으로 메모리를 할당받는 시간이 추가로 소요되며 할당 정보를 저장하는 공간까지 추가로 들어가고, vector가 동적 크기의 배열임에도 시간 복잡도를 유지하는 메커니즘 때문에 실제로 사용하는 원소보다 훨씬 많은 메모리를 할당받게 될 수도 있습니다.

중요한 건 이런 차이는 어차피 미세하기 때문에 메모리 초과를 발생시키는 원인은 아니고, 근본적으로 메모리가 의도한 것보다 어디서 많이 할당되는지를 봐야 합니다. 이 코드의 문제는 다익스트라의 구현이 잘못된 것에 있습니다. 다익스트라 알고리즘에서는 절대로 하나의 정점에 대해 그에 연결된 간선들을 두 번 이상 보게 되는 일이 있어서는 안 됩니다. 그런데 이 코드는 dp의 갱신 여부에 관계 없이 무조건 pq에 정점을 삽입하고 있으므로, (최단 거리, 정점 번호)의 쌍이 여러 번 큐에서 나오게 됩니다. 최단 거리는 24번째 줄에서 걸러지지 않으므로, 이미 이전에 해당 정점을 확인했더라도 또 다시 그에 연결된 정점들을 체크하고, 또 다시 연결 여부에 관계 없이 그에 연결된 정점들이 중복하여 큐에 들어가게 됩니다. 이것이 연쇄적으로 일어난다면, 큐에 어마어마한 수의 원소가 들어가게 될 것입니다.

자세한 것은 http://www.secmem.org/blog/201... 를 참고하세요.

ohyeaha 2년 전 0

@djm03178 님 감사합니다.

어떤 부분이 문제가 되는지 감을 좀 잡은거 같아요. dp 갱신할 때 min이 아니라 if로 체크하고 pq에 중복으로 삽입되지 않도록 해야 되네요.

현재 통과는 했지만 800ms 넘어서 아슬아슬 합니다. 다익스트라 최적화에 대해 알아보고 고민해보겠습니다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int INF = 1000000000;
int V, E, start;
int dp[20001];
vector<pair<int, int>> arr[20001];

struct MyLess {
    bool operator() (pair<int,int> a, pair<int,int> b) {
        return a.first > b.first;
    }
};

void dikstra(int start) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, MyLess> pq;
    pq.push(make_pair(0, start));

    for (int i = 1; i <= V; i++) {
        dp[i] = INF;
    }
    dp[start] = 0;

    while (!pq.empty()) {
        auto temp = pq.top();
        pq.pop();
        if (dp[temp.second] < temp.first) continue;

        for (auto& itr : arr[temp.second]) {
            int next = itr.first;
            int nextDistance = temp.first + itr.second;
            if (dp[next] > nextDistance) {
                dp[next] = nextDistance;
                pq.push(make_pair(nextDistance, next));
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> V >> E;
    cin >> start;

    int u, v, w;
    for (int i = 0; i < E; i++) {
        cin >> u >> v >> w;
        arr[u].push_back(make_pair(v, w));
    }

    dikstra(start);
    for (int i = 1; i <= V; i++) {
        dp[i] >= INF
                ? cout << "INF" << endl
                          : cout << dp[i] << endl;
    }
    return 0;
}

djm03178 2년 전 1

시간 문제는 아마 https://www.acmicpc.net/proble... 를 먼저 풀어보시면 해결됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리 초과 이유를 알고 싶습니다.

ohyeaha 2년 전 0

djm03178 2년 전 2

ohyeaha 2년 전 0

djm03178 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말