RTE 관련하여, 메모리 사용량 문의 드립니다.

  • gloryof11
    gloryof11

    ROUTING

    안녕하세요 다익스트라 알고리즘을 공부하고 ROUTING 문제를 풀어 보았습니다.

    하지만, RTE가 발생하여 답답한 상황에 있습니다;;
    (RTE (SIGKILL: program was forcefully killed, probably memory limit exceeded))

    제 생각에는, 메모리 제한이 65536KB 일때,
    256KB*256KB = 65536KB 이므로 이론상 g[32768][32768] 배열을 만들수 있어 보입니다;
    (근거.32768 * float(8byte) = 262144 byte = 256 KB)

    즉, 생성한 배열 g[10000][10000] 은 float 를 8byte 로 했을때 충분해 보이는데, 왜 RTE 가 발생하는지 잘 모르겠습니다;;;

    계산상 실수가 있는지.. 다른 원인이 있는지 고수님들의 조언을 부탁드립니다.

    감사합니다. 좋은 하루 보내세요!.

    #include <stdio.h>
    //#include <time.h>
    
    #define NUM 10000
    
    int C;
    int NN; // number of computers ; NN <= NUM
    int edge;   // 최대 20000 개
    float g[NUM][NUM];  // 배열로 잡을 수 있는 크기는? 10억까지는 괜찮음..
    float result;
    float max;
    
    float dijkstra(int src, int dest)
    {
        int N[NUM];
        int Ni = 0;
        float d[NUM];
        int p[NUM];
    
        float low = max;
        int lowi = -1;
    
        // init & set d[]
        N[src] = 1;
        Ni = 1;
        for(int i=0;i<dest;i++) {
            d[i] = g[src][i];
            p[i] = -1;
        }
    
        while(Ni<NUM) { // dest ??
            /* 여기서 선언하면 NUM 이 큰 경우 죽는다..??? */
            //float low = max;
            //int lowi = -1;
    
            // find shortest path
            for(int i=0;i<dest;i++) {
                if(d[i] != -1 && d[i] != 0 && N[i] != 1 && low > d[i]) {
                    low = d[i];
                    lowi = i;
                }
            }
            N[lowi] = 1;
            Ni++;
    
            // update shortest path
            for(int i=0;i<dest;i++) {
                if(g[lowi][i] != -1 && g[lowi][i] != 0 && N[i] != 1) {
                    if(d[i] == -1 || d[i] == 0 || d[i] > d[lowi] * g[lowi][i]) {
                        d[i] = d[lowi] * g[lowi][i];
                        p[i] = lowi;
                    }
                }
            }
        }
    
        return d[dest-1];
    }
    
    int main(void)
    {
        //clock_t st = clock();
    
        //freopen("input2.txt", "r", stdin);
        //setbuf(stdout, NULL);
    
        scanf("%d",&C);
        for(int i=0;i<C;i++)
        {
            scanf("%d %d", &NN, &edge);
    
            // init matrix
            for(int j=0;j<NUM;j++) {
                for(int k=0;k<NUM;k++) {
                    g[j][k] = -1;
                }
                g[j][j] = 0;
            }
    
            max = 0;    // to find max edge
    
            // make matrix
            for(int j=0;j<edge;j++) {
                int x, y;
                float w;
                scanf("%d %d %f", &x, &y, &w);
    
                if(max < w)
                    max = w;
    
                if(g[x][y] == -1 || (g[x][y] != -1 && g[x][y] > w))
                    g[x][y] = g[y][x] = w;
            }
    
            max = max + 1;
    
            if(NN == 0 || NN == 1)
                result = 0;
            else
                result = dijkstra(0, NN);
    
            printf("%.10f\n", result);
        }   
    
        //printf("time : %d\n",clock()-st);
    
        return 0;
    }
    


    5년 전
2개의 댓글이 있습니다.
  • Being
    Being

    네, 계산상 실수가 있습니다. 차근히 다시 계산해 보세요. 10000 * 10000 개의 4바이트 원소가 있다면 총 400 메가바이트입니다.


    5년 전 link
  • gloryof11
    gloryof11

    256*256*256 개 즉 g[4096][4096] 만큼만 만들수 있군요;;
    감사합니다^^;;


    5년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.