알고리즘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