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 문자열 자체를 출력하는 알고리즘은 어떤게 있을까요?
여기까지 하셨으면 이 질문에 대한 대답은 쉽게 구하실것이라 생각합니다. 이 부분은 다음에 포스팅하도록 하겠습니다.
읽어주셔서 감사합니다 ~
- 이 포스팅은 이곳이 출처
'프로그래밍' 카테고리의 다른 글
python List 조작법 : Extended Slices (0) | 2018.02.17 |
---|---|
[DP] Palindrome, 팰린드롬(회문) 만들기 - 2부 (0) | 2018.02.15 |
Palindrome, 팰린드롬(회문) 만들기 - 1부 (0) | 2018.02.14 |
[DP] 게임을 위한 최적의 전략 (1) | 2018.02.13 |
python 의 변경가능(Mutable) vs 변경불가능(Immutable) 객체들 (0) | 2018.02.13 |