[DP] LCS(Longest Common Subsequence) 찾기

DP 연습문제 : LCS(Longest Common Subsequence) 찾기

동적 계획법에서 굉장히 유명한 문제입니다. 알아두시면 프로그래밍 문제를 푸는데 큰 도움이 되실것이라 생각합니다.

문제

2개의 문자열이 주어집니다. 이 둘의 공통된 가장 긴 문자열을 찾으세요. 공통된 문자열은 서로 왼쪽에서 오른쪽 순으로 이어져야 하며, 한 문자열 내에서 꼭 근접한 문자들을 고르지 않아도 됩니다. 예를 들어 "abc", "abg", "bdf", "aeg", "acefg", .. 등등 은 "abcdefg" 의 부분 문자열입니다. ("gfe" 는 거꾸로 적혔으니까 안됩니다.)
그러니까 $n$ 개의 문자열이 있다면 $2^n$ 개의 부분문자열의 경우의 수가 있습니다.

이 문제는 컴퓨터과학 문제중 가장 기본적인 문제면서도 diff 라는 두 파일을 비교하는 프로그램을 만드는데 가장 핵심이 됩니다. 또한 생물정보학의 응용에서도 쓰여지고 있구요.

예제

"ABCDGH" 그리고 "AEDFHR" 의 LCS 는 "ADH" 로 길이가 3 입니다.
"AGGTAB" 그리고 "GXTXAYB" 의 LCS 는 "GTAB" 로 길이가 4 입니다.

여기에서 문제를 풀어보실 수 있습니다. 문제를 풀고 정답을 보시기를 추천드립니다.

---

정답

이 문제의 가장 기본적인 솔루션은 주어진 문자열들의 모든 부분문자열들을 만들어보고 그중에서 서로 맞는 가장 긴 부분문자열을 고르면 되는것입니다. 이 솔루션은 지수형의 시간복잡도를 가집니다. 꽤 오래걸립니다. 일단 이 문제가 왜 동적계획법(DP) 로 풀어야 하는지 알아보기로 하겠습니다.

1. 최적의 서브구조 :
주어진 문자열의 길이를 각각 m, n 이라 하고 각 문자열을 배열로 표현하자면 X[0..m-1] 그리고 Y[0..n-1] 가 된다고 가정하겠습니다. 이제 L(X[0..m-1], Y[0..n-1]) 는 두 문자열 X 와 Y의 LCS 의 길이를 반환하는 함수라고 하겠습니다. 아래에 설명드릴 내용은 L(X[0..m-1], Y[0..n-1]) 를 재귀적으로 이용한것과 같습니다.

만약 두 문자열의 마지막 문자가 같다면 (또는 X[m-1] == Y[n-1])
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2]) 가 됩니다.
즉, 뒤에서 부터 ,같은 문자를 찾으면, LCS 의 길이를 1 증가시키고 각 문자열을 하나씩 줄인뒤 다시 LCS 를 찾는 재귀형식으로 접근하는 것입니다.

만약 두 문자열의 마지막 문자가 같지 않다면 (또는 X[m-1] != Y[n-1])
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])가 됩니다.
즉, 서로 문자가 같지 않으므로 다음으로 넘어가야 하는데, 두 문자열중 하나만 다음으로 넘어가고 하나는 그대로 냅두는 방법을 택합니다. 그래서 한쪽의 문자열의 길이는 -1 이 되고 (예를 들어 m-1 -> m-2), 한쪽은 그대로 남습니다. (예를 들어 n-1 -> n-1). 그리고 그 문자열들중에 LCS를 다시 찾아서 가장 '긴' 문자열을 찾습니다. (MAX)

예제

1) "AGGTAB" 와 "GXTXAYB" 가 LCS 를 구해야할 두개의 문자열이라고 가정하겠습니다. 마지막 문자 'B' 가 서로 같네요. 그렇다면 LCS 는 위에 언급한것 처럼,

L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

로 쓸 수 있고, 이것은 다시

L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)

로 표현할 수 있습니다.

2) 다른 문자열 예시를 한번 들어보겠습니다. "ABCDGH" 와 "AEDFHR" 가 LCS 를 구해야할 두개의 문자열이라고 가정하겠습니다. 마지막 문자열은 'H' 와 'R' 로 서로 매칭이 안되네요. 그렇다면 LCS는 위에 언급한것 처럼,

L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

로 쓸 수 있고, 이것은 다시

L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFHR”), L(“ABCDGH”, “AEDFH”) )

로 표현할 수 있습니다.

이런 재귀적인 상황을 살펴보면, 주 LCS 문제는 서브 LCS 문제의 솔루션을 이용해서 풀릴 수 있다는 점이 '최적의 서브구조' 성질을 만족함을 알 수 있습니다.

2. 중복되는 서브문제들 :

아래에 작성된 코드는 LCS 문제의 재귀적 해결방법 입니다. 알고리즘 자체는 위에 언급된 공식을 따라 작성했습니다.

# python 을 이용한 LCS 문제 해결을 위한 재귀적 솔루션

def lcs(X, Y, m, n):

    if m == 0 or n == 0:
       return 0;
    elif X[m-1] == Y[n-1]:
       return 1 + lcs(X, Y, m-1, n-1);
    else:
       return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

# 테스트를 위한 드라이버 프로그램
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X , Y, len(X), len(Y))

출력값

Length of LCS is 4

위에 작성된 LCS 의 단순 접근방법의 시간복잡도는 $O(2^n)$ 입니다. 최악의 경우의 시간복잡도 입니다. 문자열 X 와 Y 가 하나도 맞는 문자가 없을때 나타나는 경우가 최악의 경우죠. 즉, LCS 의 문자열의 개수는 0 이 되는 상황입니다.

위 프로그램의 실행 중에 부분 문자열 AXYT 과 AYZX 의 부분 재귀 트리는 아래와 같습니다.

                         lcs("AXYT", "AYZX")
                       /                 \
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /             \                 /               \
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

위의 부분 재귀 트리를 보시면 lcs("AXY", "AYZ") 가 두번 중복해서 실행되는것을 보실 수 있습니다. 같은 문제를 두번 풀게 만드는거죠. 만약에 부분이 아니라 전체의 재귀 트리를 그린다면 더 많은 서브 문제들이 중복되서 풀리고 또 풀리게 될겁니다. 그래서 이 문제는 중복되는 '서브문제 성질'을 가진다고 말하고, 이런 중복되는 계산을 피하기 위해서 Memozation 또는 tabulation 을 이용해야 합니다. 아래는 LCS 문제를 풀기위해 tabulation 을 적용한 솔루션 입니다.

# DP 를 적용한 LCS 문제 솔루션

def lcs(X , Y):
    # 주어진 문자열의 길이를 구함.
    m = len(X)
    n = len(Y)

    # DP 값을 저장하기 위한 배열을 선언
    L = [[None]*(n+1) for i in xrange(m+1)]

    """L[m+1][n+1] 를 bottom up 방식으로 채워나갑니다.
    참고: L[i][j] 은  X[0..i-1] 와 Y[0..j-1] 의 LCS 길이를 가지고 있습니다."""
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0 :
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1]+1
            else:
                L[i][j] = max(L[i-1][j] , L[i][j-1])

    # L[m][n] 은 X[0..n-1] & Y[0..m-1] 의 LCS 의 길이가 저장되어 있습니다.
    return L[m][n]
#LCS 함수의 마지막

# 위의 알고리즘을 테스트 하기 위한 드라이버 프로그램
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X, Y)

# 이 코드는 Nikhil Kumar Singh(nickzuck_007) 에 의해 작성되었습니다.

위의 코드에서 DP 배열은 다음과 같이 채워집니다.

배열을 쉽게 구분하기 위해 각 문자열의 첫번째 자리 index를 1 로 설정했습니다. (index 0 인 부분은 Φ (빈자리)로 처리) 'G' 부터 보겠습니다. 'G' 와 'A' 는 서로 공통된 부분이 없으므로 LCS 는 없습니다. 그래서 table[1][1] = 0 이 됩니다.

     Φ A G G T A B
    ----------------
Φ  | 0 0 0 0 0 0 0
G  | 0 0 
X  | 
T  |  
X  |  
A  | 
Y  | 
B  |

'G'와 'AG' 는 'G' 라는 LCS 가 있습니다. 그러니까 LCS 의 길이는 1 이므로 table[1][2] = 1 이 됩니다. 이때 이 1의 값은 대각선 방향으로 넘어오는 값입니다. 즉, 아무것도 없는 공백 '' 과 'A' 를 나타내는 table[0][1] = 0 에서 + 1 을 하게되면 table[1][2] = 1 이 되는것 입니다.
이것은 위에서 언급한 : 양쪽 문자열의 끝이 일치할 경우, L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2]) 의 공식과 일치합니다.

     Φ A G G T A B
    ----------------
Φ  | 0 0 0 0 0 0 0
G  | 0 0 1
X  | 
T  |  
X  |  
A  | 
Y  | 
B  |

'G'와 'AGG' 는 역시 'G' 라는 LCS 가 있습니다. 한쪽 문자열이 하나밖에 없으므로 'G'가 다른쪽 문자열에 두개 있다 하더라도 LCS 가 2배가 될 수는 없겠죠? 그러므로 LCS 는 여전히 1 이므로 table[1][3] = 1 이 됩니다. 이때 1 의 값은 위와 왼쪽의 값중 큰 값을 가져옵니다. 즉 table[0][3] = 0('' & 'AGG') 과 table[1][2] = 1 ('G' & 'AG') 중에 더 큰 값을 찾는것이므로 table[1][3] = table[1][2] 가 됩니다.
이것은 위에서 언급한 : 양쪽 문자열의 끝이 다를경우, L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]) 의 공식과 일치합니다.

     Φ A G G T A B
    ----------------
Φ  | 0 0 0 0 0 0 0
G  | 0 0 1 1
X  | 
T  |  
X  |  
A  | 
Y  | 
B  |

마찬가지 방식으로 계속 테이블을 채워 나갑니다.
'X' 부분은 일치하는 문자가 하나도 없네요.

     Φ A G G T A B
    ----------------
Φ  | 0 0 0 0 0 0 0
G  | 0 0 1 1 1 1 1
X  | 0 0 1 1 1 1 1
T  |  
X  |  
A  | 
Y  | 
B  |

'T' 에서는 'GXT' 와 'AGGT' 부분에서 LCS 가 'GT' 가 되어 값이 2가 되는 경우를 보입니다. 즉, table[3][4] = table[2][3] + 1 이 됩니다.

     Φ A G G T A B
    ----------------
Φ  | 0 0 0 0 0 0 0
G  | 0 0 1 1 1 1 1
X  | 0 0 1 1 1 1 1
T  | 0 0 1 1 2 
X  |  
A  | 
Y  | 
B  |

나머지도 위와 같은 방식으로 전부 채우면 최종 테이블은 다음과 같습니다.

     Φ A G G T A B
    ----------------
Φ  | 0 0 0 0 0 0 0
G  | 0 0 1 1 1 1 1
X  | 0 0 1 1 1 1 1
T  | 0 0 1 1 2 2 2
X  | 0 0 1 1 2 2 2 
A  | 0 1 1 1 2 3 3
Y  | 0 1 1 1 2 3 3
B  | 0 1 1 1 2 3 4

최종적인 LCS 는 'GTAB' 가 되고 값은 table[7][6] = 4 이 됩니다.

위의 프로그램 실행의 시간 복잡도는 $O(mn)$ 입니다. 맨 처음 언급된 단순 풀이로 접근하는 방법보다 훨씬 나은 시간 복잡도를 가지고 있네요.

---

이 문제는 오직 LCS 의 길이만 요구합니다. LCS 문자열 자체를 출력하는 알고리즘은 어떤게 있을까요?
여기까지 하셨으면 이 질문에 대한 대답은 쉽게 구하실것이라 생각합니다. 이 부분은 다음에 포스팅하도록 하겠습니다.

읽어주셔서 감사합니다 ~

• 이 포스팅은 이곳이 출처