종만북에 나오는 재귀다이나믹에 대하여..(혼자 고민하니 너무 답답해요ㅠㅠ)

  • 7041701
    7041701

    종만북을 읽고 재귀다이나믹으로 거의 대부분의 다이나믹문제를 풀어오다가
    최근에 2문제가 내부적으로 스택오버플로우가 걸리는 일이 발생했습니다

    문제1.
    http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=950&sca=50&sfl=wr_subject&stx=%EA%B2%BD%EB%A1%9C&sop=and

    제가짠 코드

    #include <stdio.h>
    int INF=-200000000;
    int N;
    int d[1011][1011];
    int cache[1011][1011][3];
    int max_(int a, int b) {return a>b?a:b;}
    int dp(int y, int x, int pre) {
        if(y<0 || y>=N || x<0 || x>=N) return INF;
        if(y==N-1 && x==N-1) return d[y][x];
        int&ret=cache[y][x][pre];
        if(ret!=101*N*N) return ret;
        ret=0;
        if(y==N-1) {
            return ret=dp(y,x+1,0)+d[y][x];
        } else {
            if(pre==0) { //왼쪽에서 왔다면
                return ret=max_(dp(y+1,x,2),dp(y,x+1,0))+d[y][x];
            } else if(pre==1) { //오른쪽에서 왔다면
                return ret=max_(dp(y+1,x,2),dp(y,x-1,1))+d[y][x];
            } else if(pre==2) { //위에서 왔다면
                ret=max_(dp(y,x+1,0),dp(y,x-1,1))+d[y][x];
                return ret=max_(ret,dp(y+1,x,2)+d[y][x]);
            }
        }
    }
    int main(void) {
        int i,j,k;
        scanf("%d",&N);
        for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d",&d[i][j]);
        for(i=0;i<N;i++) for(j=0;j<N;j++) for(k=0;k<3;k++) cache[i][j][k]=101*N*N;
    
        int max=dp(1,0,2)+d[0][0];
        int temp=dp(0,1,0)+d[0][0];
        if(max<temp) max=temp;
        printf("%d",max);
        return 0;
    }
    

    문제2)
    http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1761&sca=50&sfl=wr_subject&stx=%EC%A0%84%EA%B5%AC&sop=and

    #include <stdio.h>
    int N,K;
    int d[222];
    int cache[222][222][22];
    int dp(int s, int e, int color) {
        int&ret=cache[s][e][color];
        if(ret!=-1) return ret;
        if(s==e) return ret=(d[s]!=color);
        int i,j;
        int temp,min;
        min=0x7fffffff;
        for(i=s;i<e;i++) {
            if(s<=i) temp=dp(s,i,color);
            if(i+1<=e) temp+=dp(i+1,e,color);
            if(min>temp) min=temp;
        }
        for(i=1;i<=K;i++) {
            if(color==i) continue;
            temp=dp(s,e,i)+1;
            if(min>temp) min=temp;
        }
        return ret=min;
    }
    int main(void) {
        int i,j,k;
        scanf("%d%d",&N,&K);
        for(i=0;i<N;i++) scanf("%d",&d[i]);
        for(i=0;i<=N;i++) for(j=0;j<=N;j++) for(k=0;k<=K;k++) cache[i][j][k]=-1;
        int dap=dp(0,N-1,1);
        int temp;
        for(i=2;i<=K;i++) {
            temp=dp(0,N-1,i);
            if(dap>temp) dap=temp;
        }
        printf("%d",dap);
        return 0;
    }
    

    둘다 스택오버플로우를 발생시키는 코드인데,

    여기서 궁금한점은, 진짜 어지간한 다이나믹은 다 재귀다이나믹으로 풀렸는데,

    위와같은 문제는 return ret=cache 하기전에 또 재귀호출을 하거나,

    내부적으로 cycle이 발생하는 경우같은데,,

    저런 유형은 그럼 절대 재귀다이나믹으로 풀수 없는건가요??
    (정말 오랫동안 심각하게 고민했는데, 도와주세요ㅠㅠ)

    일단 두문제다 배열다이나믹으로 풀긴풀었으나,

    위 문제유형에 대한 재귀다이나믹 풀이법을 알고싶습니다!!!


    4년 전
1개의 댓글이 있습니다.
  • Being
    Being

    운영진 권한으로 글 형식을 수정하였으니 다음부터는 맞추어 올려주시길 바랍니다.

    계산적으로 말해서 recursion과 iteration은 동등합니다. 많은 경우 재귀가 편한 이유는 우리가 call stack을 활용하여 순간의 맥락을 저장해 두었다가 함수가 되돌려지면 원래 상태를 복원할 수 있기 때문입니다. 그러나 call stack이 보통 이런 용도로 만들어진 것은 아니기 때문에 지정된 크기 이상으로 호출이 발생하면 stack overflow가 발생하는 것이죠.

    그러면 어떻게 해결하면 되느냐?

    1. Call stack의 사이즈를 늘립니다. 이건 OS와 컴파일러에 따라 다릅니다.
    2. 스택과 재귀 함수 호출 방식을 직접 구현합니다.

    특히 2번 방안의 경우 DFS 등의 알고리즘을 큰 그래프에서 구현할 때 call stack을 사용하면 쉽게 스택이 넘치기 때문에 주로 많이 사용합니다.


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