DP를 사용하는 알고리즘들 #1

Longest Increasing Subsequence

 

Problem : S에서 제일 긴 increasing subsequence 의 길이 구하기.

 

방법 1.

방법2. 

Edit Distance

 

Motivation : 어떤 단어와 ‘비슷한 (가까운)’ 단어는 어떻게 정의할 수 있을까?

 

String S1 와 S2 간의 edit distance 는 S1 에서 아래 3가지 type 의 연산을 최소한 몇 번 수행하여 S2 를 만들수 있는가로 정의한다.

1.Insertion (삽입) : S1 에 symbol 하나를 추가 (위치는 무관)

  ex) MONDT à MONEDT

2.Deletion (제거) : S1 에 symbol 하나를 제거 (위치는 무관)

  ex) MONEDT à MONED

3.Substitution (교체) : S1 에 symbol 하나를 다른 symbol로 바꿈 (위치는 무관)

  ex) MONED à MONEY

Case 1 : S1 채워져 있는 column : S1 에서 deletion

Case 2 : S2 채워져 있는 column : S1 에서 insertion

Case 3 : S1, S2 모두 채워져 있지만 symbol 이 서로 다른 column: S1 에서 substitution.

 

Key observation : S1, S2 의 gap table 에서 마지막 column 을 제거한 table 은 이에 해당되는 S1 과 S2 의 prefix 간의 edit distance 를 나타낸다

SNOW와 SUNNY를 예로 풀어보자

 

중간결과 저장에 사용

-Memorization structure : 모든 1 ≤ i ≤ n, 1 ≤ j ≤ m 에 대해 Edit (i, j) 를 저장해야 하므로 2 차원 array Edit[0…n, 0…m] 를 사용.

 

시간 복잡도는 O(mn)