Taewon Kim
6. Dynamic Programming (2) LIS, Edit distance


Sanjoy Dasgupta가 저술한 책인 Algorithms을 참고하였다.


1-1. LIS(Longest Increasing Subsequence. 최장증가순열)

앞에서부터 뒤로 수열의 부분수열을 구성할 때, 증가하는 순서대로 숫자를 고르면서 부분수열의 길이가 최대인 수열을 구하는 알고리즘

간단히 눈으로 구할 수 있는 LIS의 예를 들어보자

5　2　8　6　3　6　9　7

위 수열에서 증가하는 순서대로 숫자를 골라보면 “5, 8, 9”, “2, 3, 6, 9”, “8, 9” … 등이 있으며 LIS는 2, 3, 6, 9임을 쉽게 알 수 있다. 하지만 만약 수열이 굉~장히 길다면? LIS를 찾는 데 시간이 굉장히 오래 걸릴 것이다.

LIS를 위해 알아두어야 할 개념 중, Lower Bound라는 것이 있다.
Lower Bound(LB) : 배열을 정렬된 상태로 유지하면서 새로운 Value가 삽입될 수 있는 가장 작은 인덱스

1　3　3　6　7　(배열의 인덱스는 1부터 시작한다.)

위에서 2와 5를 삽입한다고 하면, “2의 LB = 2”, “5의 LB = 4”이다.


이제 LIS 알고리즘을 자세히 알아보자. 먼저 편의를 위해 다음과 같은 정의를 한다.

$L$ : 증가부분수열, 　$L(\max)$ : $L$의 마지막 원소(가장 큰 원소),
$x$ : 현재 탐색하고 있는 원소, 　$i$ : $x$의 Lower Bound, 　$L(i)$ : $L$의 $i$번째 원소

  1. $L$이 비어있거나 $L(\max)$ < $x$인 경우 : $x$를 $L$의 마지막 원소로 추가

  2. $L(\max)$ > $x$인 경우 : $x$의 Lower Bound $i$를 구해 대체

    2-1. $L(i) < x$ 인 경우 : $L(i)$의 오른쪽 원소를 $x$로 대체

    2-2. $L(i) > x$인 경우 : $L(i)$를 $x$로 대체

글로만 보면 무슨말인지 이해하기 힘들다. 이제 예시를 통해 LIS에 대한 자세한 이해를 해보자.


다음과 같은 수열을 바탕으로 증가부분수열 $L$을 만들어보자.

3　2　5　2　3　1　4

  1. 먼저, $L$이 비어있으므로 3을 넣어준다.

    3

  2. 그 다음 2를 보자. $L(\max) = 3　> 　2$이므로 2의 LB를 구한다. 2의 LB는 1이다. 그리고 $L(i)$ = $L(1) = 3$이므로 3과 2를 비교한다. 3 > 2이므로 위에서 2-2 설명대로 3을 2로 대체해준다.

    2

  3. 그 다음 5를 보자. $L(\max) = 2　<　5$이므로 5를 $L$의 마지막 원소로 추가한다.

    2　5

  4. 그 다음 2를 보자. 이미 $L$에 2가 있으므로 넘어간다.

  5. 그 다음 3을 보자. $L(\max) = 5　>　3$이므로 3의 LB를 구한다. 3의 LB는 2이다. 그리고 $L(i) = L(2) = 5$이므로 5와 3을 비교한다. 5 > 3이므로 위에서 2-2 설명대로 5를 3으로 대체해준다.

    2　3

  6. 그 다음 1을 보자. $L(\max) = 3　>　1$이므로 1의 LB를 구한다. 1의 LB는 1이다. 그리고 $L(i) = L(1) = 2$이므로 2와 1을 비교한다. 2 > 1이므로 위에서 2-2 설명대로 2를 1로 대체해준다.

    1　3

  7. 마지막으로 4를 보자. $L(\max) = 3 < 4$이므로 4를 $L$의 마지막 원소로 추가한다.

    1　3　4


1-2. LIS의 시간복잡도

먼저 수열의 앞에서부터 차례대로 뒤로 가며 탐색하므로 수열의 원소 개수 $O(n)$만큼 시간이 소요된다. 그리고 Lower Bound를 찾아 새로 탐색되는 원소가 놓여질 최적의 위치를 탐색해야하고, 이 과정에서 Binary Search가 사용되므로 Binary Search의 시간복잡도인 $O(\log n)$시간이 소요된다. 따라서 최종 시간복잡도는 이들의 곱인 $O(n\log n)$이다.


[참고]

만약 위 LIS 알고리즘을 사용하지 않고, 조금 무식한 아래와 같은 방법을 사용한다고 하자.

$L(j)$ : $j$번째 원소를 마지막으로 하는 LIS의 길이 = $j$번째 원소가 추가될 수 있는 증가부분수열의 길이 + 1

for $j = 1, 2, \dots , n$ :

　$L(j) = \max(L(j) : (i, j) \in E) + 1$

return $max_j L(j)$

위 방법을 사용하게 된다면, $L(i)$의 계산은 $\vert E \vert$ 내에 전체 수행시간이 선형으로 주어진 $j$의 입사차수에 비례하게 되고, $\vert E \vert < \vert V^2 \vert$ 이므로 최종 시간복잡도는 $O(n^2)$이 된다.


2-1. Edit Distance(편집거리 알고리즘)

문자열간의 유사도를 알아내는 알고리즘. 두 문자열이 같아지기 위해 필요한 최소 삽입, 연산, 대체의 최소 횟수를 구한다.

간단한 예를 들어보자.

A = delegate

B = delete

A의 5, 6번째 문자를 삭제하면 B와 같아진다. 따라서 연산횟수는 2이다.

A = process

B = professor

A의 4번째 문자를 f로 대체하고 마지막 위치에 o, r을 삽입하면 B와 같아진다. 따라서 연산횟수는 3이다.

근데 만약 이 비교대상 문자열들이 매우 길다면? 연산횟수를 구하는 데에 매우 오랜 시간이 소요될 것이다. 따라서 이를 위해 Edit Distance를 이용한다.


2-2. Edit Distance(편집거리 알고리즘) 구현 과정

Edit Distance의 알고리즘은 말로 설명하기 힘들다. 바로 예시를 통해 이해해보자.

A = azced

B = abcedf

Edit Distance를 구현하기 위해, 먼저 다음과 같이 연산 횟수 표를 작성한다.
세로에 A, 가로에 B를 공집합부터 시작해 한 문자씩 넣고 공집합과 공집합은 같으므로 연산횟수가 0이기 때문에 0을 넣어준다.

  $\emptyset$ a b c d e f
$\emptyset$ 0            
a              
z              
c              
e              
d              

그 다음, 각 셀에 숫자를 넣어줘야 한다. 규칙은 다음과 같다.

문자열 $A, B$가 있고, 표를 $D$, 표의 $i$행, $j$열의 값을 $D(i, j)$라 할 때,

  1. $A[i] = B[j] 　\rightarrow 　D(i, j) = D(i-1, j-1)$
  2. $A[i] \neq B[j]　 \rightarrow　D(i, j) = \min(D(i-1, j), 　D(i, j-1), 　D(i-1, j-1)) + 1$

쉽게 설명하면 다음과 같다.

  1. 행 - 열이 같은 경우 : 왼쪽 위 숫자 가져오기
  2. 행 - 열이 다른 경우 : 왼쪽, 왼쪽 위, 위 숫자 중 최솟값에 1을 더해 가져오기

이 규칙을 이용해 차근차근 표를 완성해보자. 최종 결과는 다음과 같다.

  $\emptyset$ a b c d e f
$\emptyset$ 0 1 2 3 4 5 6
a 1 0 1 2 3 4 5
z 2 1 1 2 3 4 5
c 3 2 2 1 2 3 4
e 4 3 2 2 2 2 3
d 5 4 4 3 2 3 3

먼저 2행부터 보자. $\emptyset \neq$ a 이므로 2행 3열의 값은 왼쪽 숫자 + 1 = 0 + 1 = 1이 된다.
그 다음 $\emptyset \neq$ b 이므로 2행 4열의 값은 왼쪽 숫자 + 1 = 1 + 1 = 2가 된다. 이렇게 쭉 2행을 완성한다.

그 다음 3행을 보자. a $\neq \emptyset$이므로 위 숫자 + 1 = 0 + 1 = 1이 된다.
그 다음 a = a 이므로 0이고, a $\neq$ b 이므로 왼쪽, 왼쪽 위, 위 중 가장 작은 숫자인 왼쪽 숫자 + 1 = 0 + 1 = 1이 된다.

이렇게 쭉~ 완성해나가면 위의 표를 얻을 수 있다. 쉽다!

이제 편집 거리를 구해보자. 편집거리 = 가장 오른쪽 하단의 수 = 3이다.


2-3. 편집 과정 구하기

그 다음으로, 완성된 편집거리 표를 바탕으로 편집 과정을 구해보자. 편집 과정은 가장 오른쪽 하단부터 왼쪽 대각선 위로 거슬러 올라가며 구한다. 과정은 다음과 같다.

  1. 오른쪽 하단 숫자부터 시작

  2. 왼쪽, 왼쪽 위, 위에서 최솟값 $S$ 찾음

  3. $S$ = 자신 = 왼쪽 위 : 변화 X

  4. $S$ < 자신일 경우

    4-1. $S$ = 왼쪽 : 열의 단어를 삭제한 것

    4-2. $S$ = 왼쪽 위 : 열의 단어를 행의 단어로 바꾼 것

    4-3. $S$ = 위 : 행에 해당하는 단어를 추가한 것

위 과정을 참고하여 아래 편집거리 표의 편집과정을 구해보자.

  $\emptyset$ a b c d e f
$\emptyset$ 0 1 2 3 4 5 6
a 1 0 1 2 3 4 5
z 2 1 1 2 3 4 5
c 3 2 2 1 2 3 4
e 4 3 2 2 2 2 3
d 5 4 4 3 2 3 3

먼저 가장 오른쪽 하단인 3부터 시작한다(3 = 자신). 왼쪽(3), 왼쪽 위(2), 위(3)에서 최솟값 $S$는 2이다.
따라서 $S$ < 자신이므로 4-1 ~ 4-3을 참고한다. $S$ = 왼쪽, $S$ = 위 이다.따라서 열의 단어 f를 삭제하고 행의 단어 d를 추가한 것을 알 수 있다.

a b c d e f　$\rightarrow$　a b c d e d

그 다음 왼쪽 대각선 위로 올라가 2로 간다(2 = 자신). 왼쪽(2), 왼쪽 위(2), 위(3)에서 최솟값 $S$는 2이다.
따라서 $S$ = 자신이므로 변화가 없다.

그 다음 왼쪽 대각선 위로 올라가 2로 간다(2 = 자신). 왼쪽(1), 왼쪽 위(2), 위(3)에서 최솟값 $S$는 1이다.
따라서 $S$ < 자신이므로 4-1 ~ 4-3을 참고한다. $S$ = 왼쪽이다. 따라서 열의 단어 d를 삭제한 것을 알 수 있다.

a b c d e d　$\rightarrow$　a b c d e

이런식으로 차근차근 올라가다보면 어떻게 대체했고 무슨 단어를 삭제했고… 등등 두 문자열이 같아지기 위한 편집과정을 알 수 있다.


2-4. Edit Distance(편집거리 알고리즘) 시간복잡도

두 문자열의 길이를 각각 $m, n$이라 할 때, $m$ x $n$ matrix를 구성하므로 부분문제의 개수가 이들의 곱인 $mn$이 된다. 그리고 왼쪽, 왼쪽 위, 위 중 최솟값을 찾는 데 걸리는 시간은 $O(1)$이므로 최종 시간복잡도는 $O(mn)$이다.


© 2020 Taewon Kim. All rights reserved.