알고리즘17-2 최장 공통 부분 서열(LCS)
longest common subsequence
subsequence는 떨어져 있을 수 있다.
substring는 연속되어야 한다.
-> substring은 subsequence
if 1
뒤에 두개가 같으면 앞의 LCS+1이 전체의 LCS이다. (편집 길이와 같은 이야기)
if 2
만약 마지막 글자가 다르다면 마지막 하나를 뺴고 LCS를 구한 것이 답
if 3
반대로 두 번쨰의 마지막 글자가 안들어간다면 빼고 구한 것이 답
1. 둘 중 하나의 길이가 0이면 0
2. 마지막 글자가 같으면 +1
3. 마지막 글자가 다르면 둘중에 큰 것
편집 길이와 같지만 change가 없다는 것이 차이.
match이므로 insert/delete만 있다.
다른 설명
shortcut을 만들어둔다.
14 (대각선을 한번도 안탔을 떄의 거리) - 4 (대각선을 탄 거리) = 10 (shortest path)
14 - 10 = 4 (LCS)
edit distance를 확장한 문제이다. 그러나 operation마다 비용이 다르다.
a->s / a->p의 비용이 다르다.
빈칸 (_) 으로 바꾸는 것이 delete
빈칸을 문자로 바꾸는 것이 insert
같은 글자들이 유사도가 크다. (대칭일수도 아닐수도)
면적이 가장 넓은 정사각형 찾기~
(직사각형은 훨씬 어려움)
n^5짜리 : 정사각형을 아무거나 잡는다.
정사각형의 변의 길이만 잡으면 다 정해진다. n^2
대각선 n개
내부 n^2
n^2짜리: edit distance와 코드가 비슷하다.
비어있는 칸이 있으면 오른쪽 아래로 하는 가장 큰 정사각형을 찾는다. 3개
3개 중에 제일 작은 것+1
