Longest Common Subsequence
최장 공통 부분 수열 (LCS,Longest Common Subsequence)
두 개 이상의 문자열 간에 가장 긴 ‘공통 부분 수열’을 찾는 문제
(‘상대적인 순서’를 유지하면서 얻을 수 있는 가장 긴 부분 수열)
brute-force로 푸는 경우는, 지수시간 (O(2^n))의 시간복잡도를 가진다
동적 계획법(DP) 적용이 가능한 문제이기에
(‘최적 부분 구조’ 와 ‘연관성’이 있는 ‘하위 문제’)
DP 적용시 O(n^2) 의 시간복잡도로 풀어낼 수 있다
(정확히는 두 문자열의 길이의 곱)
LCS의 ‘최적 부분 구조’
두 문자열 A 와 B가 주어졌을 때,
A = {a1,a2….an} 이며,
B = {b1,b2…bm} 이라 한다면
두 문자열의 LCS인 C를
C = {c1,c2…..ck} 라 가정해보자
- an = bm 이라면, ck = an = bm 이며,
C(k-1) 은 A(n-1) 과 B(m-1)의 LCS 이다 - an != bm 이고, ck != an 인 경우
C는 A(n-1)과 B의 LCS 이다 - an != bm 이고, ck != bm 인 경우
C는 A과 B(m-1)의 LCS 이다
LCS의 재귀해
i,j (이들은 각각 A,B의 임의의 인덱스)를
LCS의 길이를 나타내는 테이블 x[i,j]로 비교하자면,
- i = 0 or j = 0 일 때, x[i,j] = 0
=> 임의의 문자열과, ‘비어있는 문자열’ 사이의 공통적인 부분은 없으므로 - i,j > 0 이며, a(i) == b(j) 일 때, x[i,j] = x[i-1,j-1] + 1
=> x[i-1,j-1]은 A(i-1)과 B(j-1)의 LCS의 길이를 표현하므로,
x[i,j]는 위의 1. 에 따라서 이전 LCS의 길이보다 1이 크다 - i,j > 0 이며, a(i) != b(j) 일 때,
x[i,j] = max(x[i-1,j],x[i,j-1])
=> 위의 2,3 에 따라, x[i,j]는 ‘A(i-1) 과 B(j)의 LCS 길이’ 와
‘A(i) 과 B(j-1)의 LCS 길이’ 중 더 큰 쪽을 선택한다 (최장 공통 부분 수열을 구하는 것이기에,
당장 두 문자열의 i,j 요소가 같지 않더라도
다음 i,j에서 2의 조건에 들어가 +1을 해줄 수 있으므로!)
- 위의 내용은 ‘개수’를 구하는 방식이지만,
개수 테이블의 역추적을 통하여 스택에 해당 원소를 집어넣는 방식으로
실제 수열을 구할 수 있다
예시 코드 (백준 9251, Python)
import sys
inp = sys.stdin.readline
MAX_INPUT_V = 1001
cTable = [[0 for i in range(MAX_INPUT_V)] for i in range(MAX_INPUT_V)]
a = inp().strip()
b = inp().strip()
# i,j 가 0인 경우는 cTable[i,j] = 0
# a[i] == b[j] 인 경우, cTable[i][j] = cTable[i-1][j-1] + 1
# a[i] != b[j] 인 경우, cTable[i][j] = max(cTable[i-1][j],cTable[i][j-1])
def checkLcsCount(a,b,cTable)->int:
aSize = len(a)
bSize = len(b)
if aSize == 0 or bSize == 0:
return 0
# 이미 i,j 가 0인 경우에 대해선
# '초기값'이 0이기에 스킵
# 1부터 Size까지 비교
# 다만 문자열 자체는 0~Size-1 까지 비교해야 하므로
# (테이블의 각 0번째는 비워둔다)
for i in range(1,aSize+1):
for j in range(1,bSize+1):
if a[i-1] == b[j-1]:
cTable[i][j] = cTable[i-1][j-1] + 1
else:
cTable[i][j] = max(cTable[i-1][j],cTable[i][j-1])
return cTable[aSize][bSize]
print(checkLcsCount(a,b,cTable))
참고
- ‘Introduction To Algorithms’의 15.4
댓글남기기