알고리즘 - 17 동적 프로그래밍 활용

행렬 경로 문제

문제 정의

- 양 또는 음의 정수 원소들로 구성도니 n x n 행렬이 주어짐

- 행렬의 왼쪽 위에서 시작하여 한 칸씩 이동해 오른쪽 아래까지 도달

- 방문한 칸에 있는 수들을 더한 값이 이 경로의 합임

 

이동 방법(제약 조건)

- 오른쪽이나 아래쪽으로만 이동 가능

- 왼쪽, 위쪽, 대각선 이동은 허용하지 않음

 

목표

- 행렬의 왼쪽 위에서 오른쪽 아래까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최대화 되도록 함

 

불법 이동의 예

- 위쪽이나 왼쪽으로 이동하여선 안됨

 

 

유효한 이동의 예시

 

 

최적 부분 구조

- c_ij를 원소 (i, j)에 이르는 최고 점수라고 정의.

- m_ij는 행렬 원소 (i, j)의 값

 

1. i = j = 1이면 원소 (1, 1)에 이르는 최고 점수를 구하는 것.

 -> 원소 (1,1)만 방문하므로 원소 (1, 1)의 값이 답

2. i = 1, j > 1이면 첫째 행의 한 원소에 이르는 최고 점수를 구하는 것

 -> 첫째 행을 따라 오른쪽으로 수평 이동하는 방법밖에 없음. 따라서, (1, j)의 바로 왼쪽 원소 (1, j-1)에 이르는

   점수 ((1, j - 1)에 이르는 유일한 점수이자 최고 점수)에 원소 (1, j)의 값을 더하면 됨.

3. i > 1, j = 1이면 첫째 열의 한 원소에 이르는 최대 점수를 구하는 것

 -> 첫째 열을 따라 수직 이동하는 방법 밖에 없음. 따라서 (i, 1)의 바로 위쪽 원소 (i-1, 1)에 이르는

   점수 ((i-1, 1)에 이르는 유일한 점수이자 최대 점수)에 원소 (i, 1)의 값을 더하면 됨

4. '1, 2, 3'의 경우가 아니면

 -> 원소 (i, j)의 바로 왼쪽 원소에 이르는 최고점수와 원소 (i, j)의 바로 위쪽 원소에 이르는 최고 점수 중 큰 것에

   원소 (i, j)의 값을 더한 것이 원소 (i, j)에 이르는 최고 점수 임.

 

 

재귀적인 알고리즘의 유사 코드

matrixPath(i, j) (i, j)에 이르는 최고 점수
{
   if (i = 1 and j = 1) then return m_11;
   else if (i=1) then return (matrixPath(1, j-1) + m_1j);
   else if (j=1) then return (matrixPath(i-1, 1) + m_i1 ;
   else return ((max(matrixPath(i-1, j), matrixPath(i, j-1)) + m_ij);
}

 

호출 트리

 

 

mathPath()에서 문제 크기가 커짐에 따라 중복 호출이 증가

=> 부분 문제들의 총 수는 n^2, 중복 호출 회수는 지수적으로 증가

 

동적 프로그래밍을 이용한 유사 코드

mathPath(n) //(n, n)에 이르는 최고 점수
{
   c[1, 1] <- m_11;
   for i<-2 to n
      c[i,1] <- m_i1 + c[i-1, 1];
   for j<-2 to n
      c[1,j] <- m_1j + c[1, j-1];
   for i<-2 to n
      for j<-2 to n
         c[i, j] <- m_1j + max(c[i-1, j], c[i, j-1]);
   return c[n, n];
}

-> Theta(n^2)의 시간 복잡도