수색…


가장 긴 공통 서브 시퀀스

동적 프로그래밍의 가장 중요한 구현 중 하나는 Longest Common Subsequence를 찾는 것입니다. 먼저 기본 용어 몇 가지를 정의 해 봅시다.

하위 시퀀스 :

서브 시퀀스는 나머지 요소의 순서를 변경하지 않고 일부 요소를 삭제하여 다른 시퀀스에서 파생 될 수있는 시퀀스입니다. ABC 라는 문자열이 있다고 가정 해 봅시다. 이 문자열에서 0 개 또는 하나 이상의 문자를 지우면이 문자열의 하위 문자열을 얻습니다. 따라서 문자열 ABC의 서브 시퀀스는 { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , " }}가됩니다. 모든 문자를 제거하더라도 빈 문자열은 하위 시퀀스가됩니다. 문자열의 각 문자에 대해 하위 시퀀스를 찾으려면 두 가지 옵션이 있습니다. 하나는 문자를 사용하거나 그렇지 않습니다. 따라서 문자열의 길이가 n 인 경우 해당 문자열의 2 n 개의 하위 시퀀스가 ​​있습니다.

가장 긴 공통 서브 시퀀스 :

이름에서 알 수 있듯이 두 문자열 사이의 모든 공통 부분 시퀀스 중에서 가장 긴 공통 부분 시퀀스 (LSC)는 최대 길이를 갖는 것입니다. 예 : "HELLOM""HMLD" 사이의 일반적인 하위 시퀀스는 "H" , "HL" , "HM" 등입니다. 여기에서 "HLL" 은 길이가 3 인 가장 긴 공통 하위 시퀀스입니다.

무차별 공격 방법 :

역 추적을 사용하여 두 문자열의 모든 하위 시퀀스를 생성 할 수 있습니다. 그런 다음이를 비교하여 공통 하위 시퀀스를 찾습니다. 최대 길이를 찾아야합니다. 우리는 이미 길이 n 의 문자열의 2 n 개의 서브 시퀀스가 ​​있음을 보았습니다. 우리의 n이 20-25를 넘으면 문제를 푸는 데 수 년이 걸릴 것입니다.

동적 프로그래밍 방법 :

예제를 통해 우리의 방법에 접근 해 봅시다. 우리는 abcdafacbcf라는 두 개의 문자열을 가지고 있다고 가정합니다. 이것들을 s1s2로 나타냅니다. 따라서이 두 문자열의 가장 긴 공통 하위 시퀀스는 길이가 4 인 "abcf"입니다 . 다시 말하지만 하위 시퀀스는 문자열에서 연속적 일 필요는 없습니다. "abcf"를 구축하기 위해, 우리는 S1과 S2에 "C"에서 "다"를 무시했다. 동적 프로그래밍을 사용하여이를 어떻게 찾을 수 있습니까?

s1의 모든 문자를 한 행에, s2의 모든 문자를 열로 갖는 테이블 (2D 배열)부터 시작하겠습니다. 여기에 테이블은 0으로 인덱싱되고 우리는 1에서부터 앞으로 문자를 넣습니다. 각 행에 대해 왼쪽에서 오른쪽으로 테이블을 탐색합니다. 우리의 테이블은 다음과 같습니다.

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

여기서 각 행과 열은 두 열 사이의 가장 긴 공통 부분 시퀀스의 길이를 나타내며 그 행과 열의 문자를 취하여 앞에있는 접두어에 추가합니다. 예를 들어 Table [2] [3]"ac""abc" 사이에서 가장 긴 공통 부분 시퀀스의 길이를 나타냅니다.

0 번째 열은 s1 의 빈 서브 시퀀스를 나타냅니다. 마찬가지로 0 번째 행은 s2 의 빈 서브 시퀀스를 나타냅니다. 문자열의 빈 하위 시퀀스를 가져 와서 다른 문자열과 일치 시키려고하면 두 번째 하위 문자열의 길이가 아무리 길어도 공통 하위 시퀀스의 길이는 0입니다. 따라서 우리는 0 번째 행과 0 번째 열을 0으로 채울 수 있습니다. 우리는 얻는다 :

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

의 시작하자. 우리가 표 [1] [1]을 채울 때, 우리는 문자열 a 와 다른 문자열 a 있고 다른 것이 없다면, 여기서 가장 긴 공통 부분 시퀀스는 무엇이 될 것인가? 여기 LCS의 길이는 1이 될 것입니다. 이제 Table [1] [2]를 보겠습니다. 문자열 ab 와 문자열 a가 있습니다. LCS의 길이는 1이 될 것입니다. 알 수 있듯이 abcd , abcda , abcdaf 와 함께 문자열 a 만 고려하기 때문에 나머지 값도 첫 번째 행에 대해 1이됩니다. 그래서 우리 테이블은 다음과 같이 보일 것입니다 :

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

2 행에는 c 가 포함됩니다. 테이블 [2] [1]은 다른 쪽의 한쪽에 교류하고있다. 그래서 LCS의 길이는 1입니다. 우리는 어디에서 1을 얻었습니까? 맨 위에서 두 하위 문자열 사이의 LCS a 를 나타냅니다. 그래서 우리가 말하고있는 것은 s1 [2]s2 [1] 가 같지 않다면 LCS의 길이는 위나 왼쪽 에있는 LCS의 길이의 최대 값이 될 것입니다. 상단에있는 LCS의 길이를 취하는 것은 s2 에서 현재의 문자를 취하지 않음을 나타냅니다. 마찬가지로 LCS의 길이를 왼쪽으로하면 LCS를 만들기 위해 s1 에서 현재 문자를 취하지 않는다는 것을 나타냅니다. 우리는 얻는다 :

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

따라서 첫 번째 수식은 다음과 같습니다.

if s2[i] is not equal to s1[j]
    Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif

Table [2] [2]에 대해 우리는 문자열 abac를 가지고 있습니다. cb 는 같지 않으므로 여기에 위쪽이나 왼쪽의 최대 값을 둡니다. 이 경우, 그것은 다시 1입니다. 그 후, 테이블 [2] [3]에 대해 우리는 문자열 abcac를가 집니다. 이번에는 행과 열 모두의 현재 값이 동일합니다. 이제 LCS의 길이는 지금까지의 LCS의 최대 길이와 같습니다. 지금까지 LCS의 최대 길이는 어떻게 얻습니까? 대각선 값을 확인합니다.이 값은 aba 가 가장 잘 일치 합니다 . 이 상태에서 현재 값에 대해 s1s2에 한 문자 더 추가했습니다. 따라서 LCS의 길이는 물론 증가 할 것입니다. 표 [2] [3]1 + 1 = 2 를 넣을 것입니다. 우리는,

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+-----+-----+

따라서 두 번째 공식은 다음과 같습니다.

if s2[i] equals to s1[j]
    Table[i][j] = Table[i-1][j-1] + 1
endif

우리는 두 경우를 모두 정의했습니다. 이 두 수식을 사용하여 전체 표를 채울 수 있습니다. 테이블을 채우면 다음과 같이 보입니다.

              0     1     2     3     4     5     6
     +-----+-----+-----+-----+-----+-----+-----+-----+
     | chʳ |     |  a  |  b  |  c  |  d  |  a  |  f  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  0  |     |  0  |  0  |  0  |  0  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  1  |  a  |  0  |  1  |  1  |  1  |  1  |  1  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  2  |  c  |  0  |  1  |  1  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  3  |  b  |  0  |  1  |  2  |  2  |  2  |  2  |  2  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  4  |  c  |  0  |  1  |  2  |  3  |  3  |  3  |  3  |
     +-----+-----+-----+-----+-----+-----+-----+-----+
  5  |  f  |  0  |  1  |  2  |  3  |  3  |  3  |  4  |
     +-----+-----+-----+-----+-----+-----+-----+-----+

s1s2 사이의 LCS의 길이는 Table [5] [6] = 4 가 될 것이다. 여기서 5와 6은 각각 s2s1 의 길이입니다. 우리의 의사 코드는 다음과 같습니다.

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

이 알고리즘의 시간 복잡도는 다음과 같습니다. O (mn) 여기서 mn 은 각 문자열의 길이를 나타냅니다.

가장 긴 공통 부분 시퀀스를 어떻게 찾을 수 있습니까? 우린 오른쪽 하단부터 시작하겠습니다. 우리는 가치가 어디에서오고 있는지 확인합니다. 테이블 [i-1] [j-1]Table [i] [j] - 1 과 같을 때 값이 대각선에서 오는 경우, 우리는 s2 [i] 또는 s1 [j] (둘 모두 똑같습니다) 대각선으로 이동하십시오. 값이 위로부터 오는 경우, 즉 Table [i-1] [j]Table [i] [j] 와 같으면 맨 위로 이동합니다. 값이 왼쪽에서 오는 경우 즉, Table [i] [j-1]Table [i] [j] 와 같으면 왼쪽으로 이동합니다. 맨 왼쪽 열 또는 맨 위 열에 도달하면 검색이 종료됩니다. 그런 다음 스택에서 값을 팝어 프린트합니다. 의사 코드 :

Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
     if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
        S.push(s1[j])   //or S.push(s2[i])
        i := i - 1
        j := j - 1
    else if Table[i-1][j] == Table[i][j]
        i := i-1
    else
        j := j-1
    endif
endwhile
while S is not empty
    print(S.pop)
endwhile

주의해야 할 점은 표 [i-1] [j]표 [i] [j-1]표 [i] [j]표 [i-1] [j-1] Table [i] [j] - 1 과 같으면 그 순간에 두 개의 LCS가있을 수 있습니다. 이 의사 코드는이 상황을 고려하지 않습니다. 여러 LCS를 찾으려면이 문제를 재귀 적으로 풀어야합니다.

이 알고리즘의 시간 복잡도는 O (max (m, n)) 입니다.

가장 길게 증가하는 서브 시퀀스

임무는 정수 배열에서 가장 긴 서브 시퀀스의 길이를 찾아 서브 시퀀스의 모든 요소가 오름차순으로 정렬되도록하는 것입니다. 예를 들어 {15, 27, 14, 38, 26, 55, 46, 65, 85} 에 대해 가장 길게 증가하는 서브 시퀀스 (LIS)의 길이는 6 이고 가장 길게 증가하는 서브 시퀀스는 {15, 27, 38, 55, 65, 85} . 다시, {3, 4, -1, 0, 6, 2, 3} LIS의 길이는 4 이고 서브 시퀀스는 {-1, 0, 2, 3} 이다. 우리는 동적 프로그래밍을 사용하여이 문제를 해결할 것입니다.

두 번째 예제를 보겠습니다 : Item = {3, 4, -1, 0, 6, 2, 3} . 우리는 동일한 시퀀스 크기의 배열 dp 를 취함으로써 시작할 것입니다. dp [i] 는 원래 시퀀스의 i 번째 항목을 포함하는 경우 LIS의 길이를 나타냅니다. 맨 처음에 우리는 각 항목마다 적어도 가장 길게 증가하는 서브 시퀀스가 ​​길이가 1 임을 알 수 있습니다. 그것은 단일 요소 자체를 고려한 것입니다. 그래서 우리는 1로 dp 배열을 초기화 할 것입니다. 우리는 두 개의 변수 ij를 가질 것입니다. 처음 나는 것 및 j는 0 일 것이다. 우리 배열은 다음과 같습니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  1  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j     i

배열 위의 숫자는 시퀀스의 해당 요소를 나타냅니다. 우리의 전략은 다음과 같습니다.

if Item[i] > Item[j]
    dp[i] := dp[j] + 1

즉, I에서 소자 J의 요소보다 큰 경우, 우리가 가진 I에서 소자를 포함 할 경우, J로 소자를 포함하는 LIS의 길이가, 길이가 1 증가 할 것을 의미한다. 이 예에서 i = 1j = 0 인 경우 Item [i]Item [j] 보다 큽니다. 그래서 dp [i] = dp [j] + 1 . 우리 배열은 다음과 같습니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j     i

각 단계에서 ji 까지 증가시킨 다음 j0으로 재설정하고 i를 증가시킵니다. 지금은 ji 에 도달 했으므로 i2로 증가시킵니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j           i

i = 2 , j = 0 일 때, Item [i]Item [j] 보다 크지 않기 때문에 아무 것도하지 않고 j를 증가시킵니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                 j     i

i = 2 , j = 1 인 경우 Item [i]Item [j] 보다 크지 않으므로 아무 것도하지 않고 j 가 한계에 도달했기 때문에 i 를 증가시키고 j0으로 재설정합니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j                 i

i = 3 , j = 0 인 경우 Item [i]Item [j] 보다 크지 않으므로 아무 작업도 수행하지 않고 j를 증가시킵니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                 j           i

i = 3 , j = 1 인 경우 Item [i]Item [j] 보다 크지 않으므로 아무 것도 수행하지 않고 j를 증가시킵니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                       j     i

i = 3 , j = 2 일 때, Item [i]Item [j] 보다 크기 때문에 dp [i] = dp [j] + 1이된다 . 그 후 j 가 한계에 도달 했으므로 다시 j0으로 재설정하고 i를 증가시킵니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  2  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j                       i

i = 4j = 0 인 경우 , 항목 [i]항목 [j] 보다 크기 때문에 dp [i] = dp [j] + 1 입니다. 그 후에 j 를 증가시킵니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  2  |  2  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                 j                 i

i = 4j = 1 인 경우 항목 [i]항목 [j] 보다 큽니다. 우리는 또한 DP를 알 수있다 [내가] DP [J] = + 1 [i]는 그것으로, 우리가 {더 나은 LIS를 얻을 수 있습니다 우리가 항목 [J]의 LIS을하는 경우 즉, 우리에게 세를 제공하고 항목을 추가합니다 3,4,6}보다 {3,6} 앞당겨졌다. 그래서 우리는 dp [i] = dp [j] + 1을 설정 합니다. 그런 다음 j 를 증가시킵니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  2  |  3  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                       j           i

i = 4j = 2 인 경우 , 항목 [i]항목 [j] 보다 큽니다. 그러나이 경우에 dp [i] = dp [j] + 1을 설정 하면 2를 얻습니다. {-1,6}은 Item [ i] . 그래서 우리는 이것을 버립니다. 전략에 조건을 추가합니다. 즉 :

if Item[i]>Item[j] and dp[i]<dp[j] + 1
    dp[i] := dp[j] + 1

j1 씩 증가시킵니다. 이 전략에 따라 dp 배열을 완료하면 다음과 같이 표시됩니다.

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  2  |  3  |  3  |  4  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                                         j     i

이제이 배열을 반복하여 LIS의 길이가 될 최대 값을 찾습니다. 우리의 의사 코드는 다음과 같습니다.

Procedure LISLength(Item):
n := Item.length
dp[] := new Array(n)
for i from 0  to n
    dp[i] := 1
end for
for i from 1 to n
    for j from 0 to i
        if Item[i]>Item[j] and dp[i]<dp[j] + 1
            dp[i] := dp[j] + 1
        end if
    end for
end for
l := -1
for i from 0 to n
    l := max(l, dp[i])
end for
Return l

이 알고리즘의 시간 복잡도는 O(n²) 여기서 n 은 시퀀스의 길이입니다.

원래 시퀀스를 찾으려면 뒤로 반복하고 길이와 일치시켜야합니다. 절차는 다음과 같습니다.

Procedure LIS(Item, dp, maxLength):
i := Item.length
while dp[i] is not equal to maxLength
    i := i - 1
end while
s = new Stack()
s.push(Item[i])
maxLength := maxLength - 1
current := Item[i]
while maxLength is not equal to 0
    i := i-1
    if dp[i] := maxLength and Item[i] < current
        current := Item[i]
        s.push(current)
        maxLength := maxLength - 1
    end if
end while
while s is not empty
    x := s.pop
    Print(s)
end while

이 알고리즘의 시간 복잡도는 O(n) 입니다.

가장 긴 회문 하위 시퀀스

주어진 문자열에서 가장 긴 회문 하위 시퀀스 (LPS)는 무엇입니까? 문자열 agbdba를 가져 가자. 이 문자열의 LPS는 길이가 5 인 abdba 입니다. 우리가 하위 서열을 찾고 있기 때문에, 원래의 문자열에서 문자가 연속적 일 필요는 없다는 것을 기억하십시오. 시퀀스의 가장 긴 회문 하위 문자열 은 길이가 3 인 bdb 입니다. 그러나 여기서 우리는 하위 시퀀스에 집중할 것입니다. 이 문제를 해결하기 위해 동적 프로그래밍을 사용할 것입니다.

처음에는 원래 시퀀스와 동일한 차원의 2D 배열을 가져옵니다. 예를 들면 : S = "agbdba" , 우리는 dp [6] [6] 배열을 취할 것입니다. 여기서 dp [i] [j] 는 문자를 s [i] 에서 s [j]로 간주 할 때 만들 수있는 LPS의 길이를 나타냅니다. 예를 들어. 문자열이 aa 라면 dp [0] [1]2를 저장합니다. 이제는 문자열의 길이를 다르게하고 가능한 한 길게 만들 수 있습니다.

길이 = 1 :
여기서 우리는 한 번에 문자를 고려하고있다. 길이가 1 인 문자열이 있다면 우리가 가질 수있는 LPS는 무엇입니까? 물론 대답은 1 입니다. 그것을 저장하는 방법? dp [i] [j] 여기서 ij 와 길이가 1 인 문자열을 나타냅니다. 그래서 우리는 dp [0] [0] , dp [1] [1] , dp [2] [2] , dp [3] [3] , dp [4] [4] , dp [ 5] ~ 1 . 우리 배열은 다음과 같습니다.

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 |   |   |   |   |   |
+---+---+---+---+---+---+---+
| 1 |   | 1 |   |   |   |   |
+---+---+---+---+---+---+---+
| 2 |   |   | 1 |   |   |   |
+---+---+---+---+---+---+---+
| 3 |   |   |   | 1 |   |   |
+---+---+---+---+---+---+---+
| 4 |   |   |   |   | 1 |   |
+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+

길이 = 2 :
이번에는 길이가 2 인 문자열을 고려해 보겠습니다. 이제 길이가 2 인 문자열을 고려하면 LPS의 최대 길이는 문자열의 두 문자가 같은 경우에만 2 가 될 수 있습니다. 그래서 우리의 전략은 다음과 같습니다 :

j := i + Length - 1
if s[i] is equal to s[j]
    dp[i][j] := 2
else
    dp[i][j] := 1

길이 = 2에 대한 전략에 따라 배열을 채우면 다음과 같이 표시됩니다.

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 |   |   |   |   |
+---+---+---+---+---+---+---+
| 1 |   | 1 | 1 |   |   |   |
+---+---+---+---+---+---+---+
| 2 |   |   | 1 | 1 |   |   |
+---+---+---+---+---+---+---+
| 3 |   |   |   | 1 | 1 |   |
+---+---+---+---+---+---+---+
| 4 |   |   |   |   | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+

길이 = 3 :
이제 우리는 원래 문자열에 대해 한 번에 3 개의 문자를 봅니다. 지금부터 우리가 할 수있는 뇌 보호 시스템 (LPS)은 다음과 같이 결정됩니다.

  • 첫 번째와 마지막 문자가 일치하면 첫 번째와 마지막 문자를 제외하면 LPS +를 만들 수있는 항목이 적어도 2 개 있습니다. 나머지 문자열에서 가장 좋은 점은 무엇입니까?
  • 처음과 마지막 문자가 일치하지 않으면 우리가 만들 수있는 뇌 보호 시스템은 이미 계산 한 첫 번째 문자 또는 마지막 문자를 제외합니다.

여름철에,

j := i + Length - 1
if s[i] is equal to s[j]
    dp[i][j] := 2 + dp[i+1][j-1]
else
    dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if

Length = 3 ~ Length = 6dp 배열을 채우면 다음과 같이됩니다.

+---+---+---+---+---+---+---+
|   | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 3 | 5 |
+---+---+---+---+---+---+---+
| 1 |   | 1 | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 2 |   |   | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 3 |   |   |   | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
| 4 |   |   |   |   | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 |   |   |   |   |   | 1 |
+---+---+---+---+---+---+---+

이것은 우리가 필요로하는 dp 배열이고 dp [0] [5] 는 LPS의 길이를 포함합니다. 우리의 절차는 다음과 같습니다 :

Procedure LPSLength(S):
n := S.length
dp[n][n]
for i from 0 to n
    dp[i][i] := 1
end for
for i from 0 to (n-2)
    if S[i] := S[i+1]
        dp[i][i+1] := 2
    else
        dp[i][i+1] := 1
    end if
end for
Length := 3
while Length <= n
    for i from 0 to (n - Length)
        j := i + Length - 1
        if S[i] is equal to s[j]
            dp[i][j] := 2 + dp[i+1][j-1]
        else
            dp[i][j] := max(dp[i+1][j], dp[i][j-1])
        end if
    end for
Length := Length + 1
end while
Return dp[0][n-1]

이 알고리즘의 시간 복잡도는 O(n²) . 여기서 n 은 주어진 문자열의 길이입니다. Longest Palindromic Subsequence 문제는 Longest Common Subsequence와 밀접하게 관련되어 있습니다. 두 번째 문자열을 첫 번째 문자열의 반대로 가져 와서 길이를 계산하고 결과를 출력하면 주어진 문자열의 가장 긴 회문 하위 시퀀스가됩니다. 이 알고리즘의 복잡성 또한 O(n²) 입니다.



Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow