[문제해결기법] 11. 동적 계획법

 

동적 계획법 (DP)

• 최적화 문제, 분할 정복
• 한 문제를 똑같은 문제이면서 크기만 작은 것으로 바꿀 수 있을지 생각해본다.
• 금화 모으기 문제
  • D[i][j] : (i, j)까지 오는 동안 모을 수 있는 금화의 최댓값
  • D[i][j] = max( D[i-1],[j] , D[i][j-1] ) + map[i][j];

 

최대 공백 정사각형 (흰색으로만 이루어진 가장 큰 정사각형)

• mm 크기의 정사각형이 있다면, 4개의 (m-1)(m-1) 크기 정사각형이 있어야 한다는 점에서 착안한다.
• D[x][y]는 (x,y)가 가장 오른쪽 아래 꼭지점인 정사각형의 최대 크기라고 가정한다.
  • (x,y)가 검은색이면, D[x][y] = 0
  • 흰색이면,
    1. x==1 && y==1 : D[x][y] = 1
    2. else : D[x][y] = min(D[x-1][y-1] , D[x-1][y] , D[x][y-1] ) + 1

 

최장 공통 부분서열 문제 (LCS) : 순서는 지키되, 연속일 필요는 없음. LCS 길이 구하기

 

1. 브루트 포스 O(2^n) : 길이가 n인 서열에 대해서 가능한 모든 2^n개의 부분 서열을 비교
2. 재귀 O(m * n) : 하나는 길이가 m, 다른 하나는 길이가 n일 때 (둘다 n이면 O(n^2))
   1. ABA와 DAB의 LCS는 아래의 셋 중 가장 큰 값일 것이다. 그 점에서 착안하여 재귀로 풀면, O(m * n). LCS(AB, DAB), LCS(ABA, DA), LCS(AB, DA)
   2. 하지만 중복 계산이 많이 발생한다는 단점이 있다.

   int lcs( char *X, char *Y, int m, int n )
   {
      if (m == 0 || n == 0)
        return 0;
      if (X[m-1] == Y[n-1])
        return 1 + lcs(X, Y, m-1, n-1); // 맨 뒤 문자가 같으면 1을 더한다.
      else
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); // 맨 뒤 문자가 다르면, 둘 중 하나를 뺀 값의 최대값을 반환
   }
    
   int main() {
     char X[] = "AGGTAB";
     char Y[] = "GXTXAYB";
     int m = strlen(X);
     int n = strlen(Y);
     printf("Length of LCS is %d\\n", lcs( X, Y, m, n ) );
   return 0; }
   

3. DP : 중복계산이 없는 O(m * n)
   1. 중간 결과를 저장하고 활용하므로 재귀보다 훨씬 효율적이고, 중복계산을 피할 수 있다.

   int lcs( char *X, char *Y, int m, int n )
   { int L[m+1][n+1];
   int i, j;
   for (i=0; i<=m; i++)   {
     for (j=0; j<=n; j++) {
       if (i == 0 || j == 0) L[i][j] = 0;
       else if (X[i] == Y[j])
   		    L[i][j] = L[i-1][j-1] + 1; // 현재 문자가 같으면 1을 더하기
       else
   		    L[i][j] = max(L[i-1][j], L[i][j-1]); // 다르면, 이전 값들 중 최대값 넣기
       }
   	}
   }
      return L[m][n];
   }
   

두 문자열의 유사도

1. Hamming Distance : 단순히 틀린 글자수만 비교한다. O(n). 매우 부정확.
2. 편집 거리 (Edit distance)
   1. 문자열 a를 b로 바꾸기 위해 다음의 연산이 최소 몇 번 필요한가?
      • 한 글자 지우기, 한 글자 추가하기, 한 글자 바꾸기
   2. 점화식 : D[i][j] = T1[1..i]을 T2[1..j]로 바꾸는 편집 거리 저장 → D[i][j]는 다음 세 값 중 최소값이다.
      • D[i][j-1] + 1 : T1[1..i]을 T2[1..j-1]로 바꾸고 마지막 문자 T2[j] 추가
      • D[i-1][j] + 1 : T1[1..i]을 마지막 글자를 빼서 T1[1..i-1]로 바꾸고 마지막 문자 추가해서 T2[1..j]로
      • D[i-1][j-1] + 0/1 : T1[1..i-1]을 T2[1..j-1]로 바꾼 다음, T1[i] == T2[j] : 그대로, else : T1[i]을 T2[j]로 바꾸는 거 한번

   // DP 코드 : O(m * n)
   int editDistDP(string str1, string str2, int m, int n)
   {
       int dp[m+1][n+1];
       for (int i=0; i<=m; i++)    {
           for (int j=0; j<=n; j++)        {
               if (i==0) dp[i][j] = j;  // Min. operations = j
               else if (j==0) dp[i][j] = i; // Min. operations = i
               else if (str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1]; // 현재 문자가 같으면
               else dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]); // 3개 중 최소의 방법에 1을 더하기
    } }
       return dp[m][n];
   }
   

    

1. 1.