다이나믹 프로그래밍 2

---

다이나믹 프로그래밍 1

위의 다이나믹 프로그래밍의 개념을 먼저 공부하고 아래의 문제를 다이나믹 프로그래밍을 이용해서 해결해 보겠습니다.

 

 

행렬 경로 문제

1. 정수들이 저장된 N * N 행렬이 있습니다.

2. 이 행렬의 좌상단 부터 우하단 까지 이동 합니다.

3. 오른쪽이나 아래쪽 방향으로만 이동 할 수 있습니다.

4. 어느 길로 가야 정수들의 합이 최소가 되도록 할 수 있을까요?

1. (i, j)에 도달하기 위해서는 (i, j-1) 혹은 (i-1, j)를 거쳐야 합니다.

2. (i, j-1) 혹은 (i-1, j)까지는 최선의 방법으로 이동해야 합니다.

 

 

1. 조건식

 

 

2. sudo 코드

int findMiniVal(int i, int j){
   if(i == 1 && j == 1)
       return m[i][j];
   else if(i == 1)
       return findMiniVal(1, j-1) + m[i][j];
   else if(j == 1)
       return findMiniVal(i-1, 1) + m[i][j];
   else
       return Math.min(findMiniVal(i-1, j), findMiniVal(i, j-1)) + m[i][j];
}

위 findMiniVal()의 호출 스택(Call stack)을 가시적으로 확인해 보겠습니다.

밑에 이미지를 보시면 i = 4, j = 4 임에도 findMiniVal() 함수가 굉장히 많이 호출 되는 것을 확인 할 수 있습니다. 이중에서 중복 되는 연산을 확인 하기 위해 findMiniVal(2, 2) 와 findMiniVal(2, 1)가 얼마나 많이 호출 되는지 체크해 봤습니다. 우리는 memoization 방식으로 이를 해결해야 합니다.

 

 

3. memoization top-down 방식

int findMiniVal(int i, int j){                   // 배열 miniSum은 이미 -1로 초기화
   if(miniSum[i][j] != -1) return miniSum[i][j]; // 기존 배열 miniSum이 -1이 아니라면 캐싱되어 있던 값 리턴
   if(i == 1 && j == 1)
       miniSum[i][j] = m[i][j];
   else if(i == 1)
       miniSum[i][j] = findMiniVal(1, j-1) + m[i][j];
   else if(j == 1)
       miniSum[i][j] = findMiniVal(i-1, 1) + m[i][j];
   else
       miniSum[i][j] = Math.min(findMiniVal(i-1, j), findMiniVal(i, j-1)) + m[i][j];
   return miniSum[i][j];
}

miniSum 이라는 2차원 배열을 만들고 이 2차원 배열은 -1값로 모두 초기화 되있어야 합니다. miniSum[i][j] 은 (i, j)까지 오른쪽이나 아래쪽으로만 이동했을때 m[i][j]의 합이 최소가 되는 값이 저장 되기 위한 공간 입니다.

 

 

4. memoization bottom-up 방식

int findMiniVal(int i, int j){           // 배열 miniSum은 이미 -1로 초기화
   for(int i=1; i<=n; i++){
       for(int j=1; j<=n; j++){
           if(i==1 && j==1)
              miniSum[i][j] = m[1][1];
           else if(i == 1) 
              miniSum[i][j] = m[i][j] + miniSum[i][j-1];
           else if(j == 1)
              miniSum[i][j] = m[i][j] + miniSum[i-1][j];
           else
              miniSum[i][j] = m[i][j] + Math.min(miniSum[i-1][j], miniSum[i][j-1]);
       }
   }
   return miniSum[n][n];
}

이 코드의 시간 복잡도는 두개 for문이 n번씩 반복 되므로 O(n2) 입니다.

 

 

5. Common trick

int findMiniVal(){             // 배열 miniSum은 이미 무한대로(-1이 아니라) 초기화
   for(int i=1; i<=n; i++){
       for(int j=1; j<=n; i++){
           if(i==1 && j==1){
              miniSum[i][j] = m[1][1];
           else
              miniSum[i][j] = m[i][j] + Math.min(miniSum [i-1][j], miniSum [i][j-1]);
       }
   }
   return miniSum[n][n];
}

위 코드는 bottom-up 방식 에서 miniSum을 -1이 아니라 무한대로 초기화 시켜 if(i == 1) 또는 if(j == 1) 조건을 지워 줄수 있습니다. -1이 아닌 무한대로 초기화 시켰으면 Math.min(miniSum[0][j], miniSum[i][j-1])은 Math.min(무한대, miniSum[i][j-1])가 되기 때문에 if(i == 1) 또는 if(j == 1) 조건을 지워 줄수 있습니다.

 

 

6. 최단 경로 구하기

위에 까지의 코드는 최소합을 구하는 방법 이었습니다. 이번에는 최소합을 따라 가는 경로를 출력해 보겠습니다.

int findMiniVal(){             // 배열 miniSum은 이미 무한대로(-1이 아니라) 초기화
   for(int i=1; i<=n; i++){
       for(int j=1; j<=n; i++){
           if(i==1 && j==1){
              miniSum[i][j] = m[1][1];
              path[i][j] = '-';
           else{
                if(miniSum[i-1][j] < miniSum[i][j-1]){
                      miniSum[i][j] = m[i][j] + miniSum[i-1][j];
                      path[i][j] = '^';
                } else {
                      miniSum[i][j] = m[i][j] + miniSum[i][j-1];
                      path[i][j] = '<';
                }
           }
       }
   }
   return miniSum[n][n];
}

 

 

6-1 도착점 부터 경로 출력하기

void printPath(){
    int i = n, j = n;
    while(path[i][j] != '-'){
        print(i + " " + j);
        if(path[i][j] == '<')
            j = j - 1;
        else
            i = i - 1;
   }
   print(i + " " + j);
}

 

 

6-2 출발점 부터 경로 출력 하기

// 위 코드와 반대로 출력 순서가 반대로 출력되고 recrusive 하게 구현
void printPathRecursive(int i, int j){
    if(path[i][j] == '-')
       print(i + " " + j);
    else {
       if(path[i][j] == '<')
          printPathRecursive(i, j-1);
       else
          printPathRecursive(i-1, j);
       print(i + " " + j);
    }
}