dynamic-programming
서브 시퀀스 관련 알고리즘
수색…
가장 긴 공통 서브 시퀀스
동적 프로그래밍의 가장 중요한 구현 중 하나는 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를 넘으면 문제를 푸는 데 수 년이 걸릴 것입니다.
동적 프로그래밍 방법 :
예제를 통해 우리의 방법에 접근 해 봅시다. 우리는 abcdaf 와 acbcf라는 두 개의 문자열을 가지고 있다고 가정합니다. 이것들을 s1 과 s2로 나타냅니다. 따라서이 두 문자열의 가장 긴 공통 하위 시퀀스는 길이가 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]에 대해 우리는 문자열 ab 와 ac를 가지고 있습니다. c 와 b 는 같지 않으므로 여기에 위쪽이나 왼쪽의 최대 값을 둡니다. 이 경우, 그것은 다시 1입니다. 그 후, 테이블 [2] [3]에 대해 우리는 문자열 abc 와 ac를가 집니다. 이번에는 행과 열 모두의 현재 값이 동일합니다. 이제 LCS의 길이는 지금까지의 LCS의 최대 길이와 같습니다. 지금까지 LCS의 최대 길이는 어떻게 얻습니까? 대각선 값을 확인합니다.이 값은 ab 와 a 가 가장 잘 일치 합니다 . 이 상태에서 현재 값에 대해 s1 과 s2에 한 문자 더 추가했습니다. 따라서 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 |
+-----+-----+-----+-----+-----+-----+-----+-----+
s1 과 s2 사이의 LCS의 길이는 Table [5] [6] = 4 가 될 것이다. 여기서 5와 6은 각각 s2 와 s1 의 길이입니다. 우리의 의사 코드는 다음과 같습니다.
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) 여기서 m 및 n 은 각 문자열의 길이를 나타냅니다.
가장 긴 공통 부분 시퀀스를 어떻게 찾을 수 있습니까? 우린 오른쪽 하단부터 시작하겠습니다. 우리는 가치가 어디에서오고 있는지 확인합니다. 테이블 [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 배열을 초기화 할 것입니다. 우리는 두 개의 변수 i 와 j를 가질 것입니다. 처음 나는 한 것 및 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 = 1 및 j = 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
각 단계에서 j 를 i 까지 증가시킨 다음 j 를 0으로 재설정하고 i를 증가시킵니다. 지금은 j 가 i 에 도달 했으므로 i 를 2로 증가시킵니다.
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 를 증가시키고 j 를 0으로 재설정합니다.
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 가 한계에 도달 했으므로 다시 j 를 0으로 재설정하고 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 = 4 및 j = 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 = 4 및 j = 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 = 4 및 j = 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
j 를 1 씩 증가시킵니다. 이 전략에 따라 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] 여기서 i 는 j 와 길이가 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 = 6 의 dp 배열을 채우면 다음과 같이됩니다.
+---+---+---+---+---+---+---+
| | 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²)
입니다.