algospot.com :: 질문과 답변: DEATH 문제 memory limite exceeded 조언 부탁드립니다.

DEATH 문제 memory limite exceeded 조언 부탁드립니다.

N^2 크기의 행렬을 이용하여 X에 대한 분할정복을 이용하여 해결하였는데, memory limit exceeded가 뜨는군요.
제 컴퓨터에서는 (맥 xcode를 사용하고 있습니다) 최고 크기의 데이터를 넣어도 잘 돌아가서, 어느 부분에서 문제가 있는지를 가늠하지 못하겠습니다.
어떤 부분을 어떻게 개선하면 좋을지 조언 부탁드립니다.

#include <memory.h>
#include <stdio.h>
#include <cassert>

double **mat_mul(double **A, double **B, int N);
double **div_con(int *A, int N, int X, int T);
void solve();

int main(int argc, const char * argv[])
{
    int T;
    scanf("%d", &T);
    while(T--)
        solve();
    scanf("%d",&T);
    return 0;
}

void solve()
{
    int N, X, M, T;
    scanf("%d%d%d%d", &N, &X, &M, &T);
    int *A, *B;
    A = new int[N];
    B = new int[M];

    for(int i=0; i<N; i++)
    {
        scanf("%d", &A[i]);
        A[i]--;
    }
    for(int i=0; i<M; i++)
    {
        scanf("%d", &B[i]);
        B[i]--;
    }


    double **C;
    C = new double * [N];
    for(int i=0; i<N; i++)
        C[i] = new double[N];
    C[0][0] = 1;

    double ** temp = div_con(A,N,X,T);
    double ** temp2 = mat_mul(C, temp, N);

    for(int i=0; i<M; i++)
        printf("%.5f\n", temp[0][B[i]]);

    for(int i=0; i<N; i++)
    {
        delete [] temp[i];
        delete [] temp2[i];
        delete [] C[i];
    }
    delete [] temp;
    delete [] temp2;
    delete [] C;
    delete [] A;
    delete [] B;
}

double **div_con(int *A, int N, int X, int T)
{
    /*
     ans[i][j] : i->j
     sum of ans[i] is always 1
     */
    double **ans;
    if(X == 0)
    {
        ans = new double * [N];
        for(int i=0; i<N; i++)
            ans[i] = new double [N];
        for(int i=0; i<N; i++)
            ans[i][i] = 1;
    }

    else if(X == 1)
    {
        ans = new double * [N];
        for(int i=0; i<N; i++)
            ans[i] = new double [N];

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

        ans[0][A[0]] = 1;
        for(int i=1; i<N; i++)
            for(int j=-T; j<=T; j++)
                ans[i][(A[i] + j +N)%N] = (double)1/(2*T + 1);
    }

    else if(X%2 == 0)
    {
        double **temp = div_con(A,N,X/2,T);
        ans = mat_mul(temp, temp, N);
        for(int i=0; i<N; i++)
            delete [] temp[i];
        delete [] temp;
    }
    else
    {
        double **temp = div_con(A,N,X/2,T);
        double **temp2 = mat_mul(temp, temp, N);
        double **temp3 = div_con(A,N,1,T);
        ans = mat_mul(temp2, temp3, N);

        for(int i=0; i<N; i++)
        {
            delete [] temp[i];
            delete [] temp2[i];
            delete [] temp3[i];
        }
        delete [] temp;
        delete [] temp2;
        delete [] temp3;
    }
    return ans;
}

double **mat_mul(double **A, double **B, int N)
{
    double **ans;
    ans = new double *[N];
    for(int i=0; i<N; i++)
        ans[i] = new double[N];

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

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            for(int k=0; k<N; k++)
                ans[i][j] += A[i][k] * B[k][j];

    return ans;
}

11년 전

10개의 댓글이 있습니다.

wookayin

질문과는 별개의 답변이지만, new [] 로 생성한 것은 free 가 아닌 delete[] 로 지워줘야 합니다.

그리고 solve(), mat_mul() 가 리턴한 포인터가 가리키는 메모리 영역이 해제되지 않는 경우가 보이네요. 'new' 로 생성한 메모리가 반드시 delete 되는 것을 보장하는지를 염두에 두고 코드를 찬찬히 살펴보세요.

11년 전 link
JongMan

아니면 vector<vector<double> >을 쓰시던가요. ;)

11년 전 link
sven

@wookayin 답변 감사합니다. 알고리즘은 맞는 것 같은데, 말씀하신 부분에서 코딩의 미숙함 때문에 memory limit exceeded가 발생하는 것 같습니다.
double **A; 꼴의 경우,
for(int i=0; i<N; i++)
delete [] A[i]
delete [] A
를 이용하여 delete를 시도했는데, 아예 실행 결과가 틀어져버리는군요.
어디서 어떤 문제가 생긴 것인지 잘 모르겠습니다.
조언 부탁드립니다.
(코드는 수정본으로 바꾸었습니다.)

@JongMan 답변 감사합니다. 그렇게도 시도해봐야겠습니다.

11년 전 link
JongMan
```
ans = mat_mul(ans, div_con(A,N,1,T), N);
```
이 줄에서 div_con에서 반환된 행렬은 영영 지워지지 않겠지요

11년 전 link
JongMan

아니 그런데.. div_con에서 X=0일 경우 무한 재귀 호출이 일어날 것 같은데 이게 로컬에선 잘 돌아 가나요?

11년 전 link
JongMan

글고 if 문 내에서 ans 를 덮어씌우는 경우 앞에서 할당했던 배열도 지워지지 않을 테고요.
이래서 vector를 쓰는 것이 중요하지요~ :)

11년 전 link
sven

@JongMan 답변 감사합니다. 나름대로 수정해보았으나 여전히 결과가 틀어지는군요. (본글의 코드는 수정본으로 업데이트하였습니다.) 실행시마다 다른 쓰레기값이 나타납니다. (delete 부분을 주석처리하면 정상적으로 작동합니다.) 배열로 구현을 성공시켜보고싶은데, 어렵네요 ㅜㅜ 메모리 관련 문제는 디버깅을 어떻게 해야할지 잘 모르겠습니다.

11년 전 link
JongMan

메모리 관련 문제는 valgrind같은 프로파일러를 돌려 보는 것이 좋지요. :-) 아마 OS X용도 있을 겁니다.

11년 전 link
sven

@JongMan Xcode 내부 메모리 누수 체크 기능이 있어, 해결하였습니다. 와중에 질문이 또 생겼는데요,
1. new 명령어는 초기화를 보장하지 않나요? 위의 코드 (정답이 뜬 수정본으로 바꿨습니다.) 에서 추가적으로 초기화해준 부분을 지우면 쓰레기값이 나타납니다. 아니면 메모리 관리가 아직도 제대로 되지 않은 것인지...
2. ps에서, vector 배열의 장단점은 어떤가요? 저는 성능 차이가 TLE에 영향을 줄 정도는 아니라고 생각하여 코딩이 단순하고 오류 발생 가능성이 적은 쪽을 택하는게 좋으리라 생각합니다. 그리고 지금과 같이 메모리에 대한 접근이 필요한 경우는 vector 가 훨씬 간단할 것 같습니다. 그런데 여기 알고스팟의 다른 분들의 코드나 주변 정올 출신 사람들의 코드를 보면 메모리를 다루더라도 항상 배열만 쓰시더라구요. 반대로 탑코더의 코더들의 경우는 vector 를 많이 쓰시는 것 같구요.

11년 전 link
JongMan

물론 저는 vector를 추천합니다. ^^ 벡터를 써서 TLE가 날 코드는 배열 써도 TLE 날꺼에요 아마.. 그리고 vector의 경우 특히 크기를 미리 ensure() 해놓으면 배열과 속도 차이 거의 없어요 ㅎ

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

SINCE 2007

다가오는 이벤트들

DEATH 문제 memory limite exceeded 조언 부탁드립니다.

10개의 댓글이 있습니다.