LCS(Longest Common Subsequence) 문제 다이나믹 프로그래밍 기본 해법 배우기
1. 문제
두 문자열 $X = x_{1}x_{2}x_{3}...x_{n}$와 $Y = y_{1}y_{2}y_{3}...y_{m}$이 주어진다.
여기서 $x_{i}$와 $y_{j}$는 하나의 문자를 나타낸다.
여기서 문자열의 부분문자열(Subsequence)은?
"원래 문자열에서 순서를 유지한채로 문자 몇개를 제거한 문자열"로 정의한다.
예를 들어 'ABCBDAB'라고 한다면... ABC도 부분문자열이지만, ABBAB도 부분문자열이 된다.
가장 긴 공통 부분문자열(Longest Common Subsequence) 문제는 K개의 문자열이 주어질때,
모든 문자열의 공통 부분문자열 중에서 가장 긴 공통 부분문자열을 구하는 문제이다.
K가 변수이면 다항시간내에 풀 수 없는 NP-hard문제임이 증명되어있다.
가장 기본 문제는 K = 2인 경우이다.
예를 들어 다음과 같이 X = 'ABCBDAB'이고 Y = 'BDCABA'라고 하자.
그러면 X,Y의 가장 긴 공통 부분문자열은 'BCBA'이다.
기초적인 문제이지만, 생물정보학에서 DNA 염기서열을 계산하여 두 DNA가 얼마나 유사한지 분석하는 문제에서 자주 사용된다.
또한 전산언어학, 실생활에서 사용하는 검색 엔진 등에서도 활용되는 아주 중요한 문제이다.
2. 해법
두 문자열의 길이가 N,M일때, 다이나믹 프로그래밍을 이용한 O(NM) 해법이 가장 기본이면서 잘 알려져있다.
해싱이나 문자의 값을 사용하지 않고 LCS를 구하기 위해서는 O(NM)번의 문자쌍 비교가 반드시 필요하다는 것이 증명되었다.
그래서 다이나믹 프로그래밍이 이 경우 최적의 알고리즘이다. (물론 더 빠른 알고리즘이 있다)
dp[i][j]를 $X = x_{1}x_{2}...x_{i}$와 $Y = y_{1}y_{2}...y_{j}$의 가장 긴 공통 부분문자열(Longest Common Subsequence)의 길이라고 정의하자.
1) 만약 두 문자 $x_{i}$와 $y_{j}$가 서로 같다면?
당연히 $x_{i} = y_{j}$인 이 문자는 두 문자열의 공통 부분문자열의 일부가 된다.
그러므로 이전까지의 부분문자열인 $x_{1}x_{2}...x_{i-1}$과 $y_{1}y_{2}...y_{j-1}$의 가장 긴 공통부분문자열의 길이에
1을 더해주면 된다.
$$dp[i][j] = dp[i-1][j-1] + 1, x_{i} = y_{j}$$
2) 하지만 $x_{i}$와 $y_{j}$가 다르다면?
그렇다면, $x_{1}x_{2}...x_{i}$와 $y_{1}y_{2}...y_{j-1}$ 사이 가장 긴 공통 부분문자열의 길이 DP[i][j-1]과
$x_{1}x_{2}...x_{i-1}$과 $y_{1}y_{2}...y_{j}$ 사이 가장 긴 공통 부분문자열의 길이 DP[i-1][j] 중
더 큰 값을 i,j까지 가장 긴 공통 부분문자열의 길이로 할 수 있다.
$$DP[i][j] = max(DP[i-1][j], DP[i][j-1]), x_{i} \neq y_{j}$$
3. 연습문제
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
위 알고리즘을 그대로 구현하면 된다
#두 문자열 s1,s2의 가장 긴 공통 부분문자열(longest common subsequence)의 길이 구하기
s1 = input()
s2 = input()
#dp[i][j]는 s1[1,2,..,i]와 s2[1,2,..,j]의 가장 긴 공통 부분문자열의 길이
dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
answer = 0
#s1[i] == s2[j]이면, s1[1,2,..,i-1]과 s2[1,2,..,j-1]의 가장 긴 공통 부분문자열의 길이에 s1[i] 하나를 더해준다
#s1[i] != s2[j]이면, s1[1,2,..,i]와 s2[1,2,..,j-1]의 가장 긴 공통 부분문자열의 길이와
#s1[1,2,..,i-1]과 s2[1,2,..,j]의 가장 긴 공통 부분문자열의 길이 중 더 큰 값이 된다
for i in range(1,len(s1)+1):
for j in range(1,len(s2)+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > answer:
answer = dp[i][j]
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
print(answer)
4. 실제 가장 긴 공통 부분문자열을 구하는 방법
가장 긴 공통 부분문자열의 길이는 알았는데, 그렇다면 진짜 공통 부분문자열은 어떻게 알 수 있을까?
dp테이블의 마지막부터 역으로 어디서 온건지 추적해나가면 알 수 있다
먼저 X = ABCDE와 Y = EBDE에 대하여 가장 긴 공통 부분문자열을 구하기 위해 DP테이블을 채우면...
이 테이블이 어떻게 채워지는가?를 한번 생각해보면
값이 서로 같은 방향으로 이동하다가, 서로 문자가 일치해서 길이가 증가하는 경우라면 대각선으로 이동하게 된다.
따라서, 테이블의 끝에서 시작해서 이것을 반대로 생각해보면....
현재 위치 i,j에 대하여... dp[i][j]값에 접근하고... dp[i][j-1]과 비교해본다.
dp[i][j-1]과 다르다면, dp[i-1][j]와 비교해본다.
dp[i-1][j]와 다르다면... $x_{i}$와 $y_{j}$가 같은 문자이며.. 해당 문자를 LCS의 문자로 저장하고 i,j를 1 감소시킨다
위 그림은 두번 연속 대각선으로 이동한 경우이다.
다시 dp[i][j]와 dp[i][j-1]을 비교해보고.. 다르다면 dp[i-1][j]와 비교해본다.
이제 dp[i][j]와 dp[i-1][j]가 서로 같으므로 i를 1 감소시킨다.
다시 dp[i][j]와 dp[i][j-1]을 비교하니 다르고 dp[i-1][j]와도 다르므로 해당 위치의 문자는 LCS에 포함되며...
대각선으로 이동
이제 dp[i][j]와 dp[i][j-1]을 비교해보면 서로 같으므로 해당 위치로 이동한다.
마지막으로 dp[i][j]와 dp[i-1][j]가 서로 같으므로 해당 위치로 이동하고, (0,0)에 도달했으니 알고리즘을 종료
따라서, LCS를 위해 DP배열을 모두 채운 다음, 마지막 (n,m)위치에서 시작해서...
1) dp[i][j] == dp[i][j-1]이면 (i,j-1) 위치로 이동
2) dp[i][j] != dp[i][j-1]이면, dp[i][j] == dp[i-1][j]이면, (i-1,j) 위치로 이동
3) dp[i][j] != dp[i-1][j]이면, 해당 위치 s1[i] == s2[j]는 LCS에 포함되는 문자이고 (i-1,j-1)로 이동
4) (0,0)에 도달하면 지금까지 읽어온 문자를 반대로 구하면 해당 문자열이 LCS이다.
5. 연습문제
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
6. 풀이
위 알고리즘을 그대로 구현하면 된다.
이렇게 역추적을 해보니까... LCS 구하는 코드를 조금 최적화했는데
첫번째 포인트는 원래 내가 LCS의 길이를 구할때 DP의 max값을 answer과 비교하면서 구했는데...
for i in range(1,len(s1)+1):
for j in range(1,len(s2)+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > answer:
answer = dp[i][j]
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
print(answer)
위에서 dp 배열을 채우는 결과를 보면 알겠지만...
LCS의 길이는 결국 DP[len(s1)][len(s2)]에 있다는 것을 알 수 있다..
그래서 이 부분을 조금 고치고...
두번째 포인트는.. 일단 위 dp[i][j]와 dp[i][j-1]을 비교했는데... 다음 그림과 같이
j가 0에 있는 경우... 애초에 위로 이동할 수가 없다
그래서 dp 비교 과정을 작성할때, j >= 1 and dp[i][j] == dp[i][j-1]로 작성해줘야한다.
세번째는 lcs의 길이는 알고 있기 때문에 처음에 배열을 lcs 길이만큼 초기화해두고...
lcs 문자를 찾았을때 lcs 배열에 역으로 채워넣다.
마지막으로.. 인덱스를 one - based로 작성했기 때문에... lcs에 넣을때는 X[i-1]로 넣어줘야한다...
#실제 LCS를 역추적하여 구하는 함수
def get_lcs(dp,n,m,X):
i = n
j = m
lcs = [0]*(dp[i][j]) #LCS의 길이는 dp[n][m]이므로.. 배열을 초기화
k = 1
#i = 0, j = 0에 도달할때까지 (n,m)부터 역으로 이동
while i != 0 or j != 0:
#j가 1이상이고, dp[i][j] == dp[i][j-1]이면, j > j-1로 이동
#j가 1이상이어야 j > j-1로 이동할 수 있기 때문...
if j >= 1 and dp[i][j] == dp[i][j-1]:
j -= 1
#dp[i][j] != dp[i][j-1]일때, dp[i][j] == dp[i-1][j]이면, i > i-1로 이동
elif dp[i][j] == dp[i-1][j]:
i -= 1
#dp[i][j] != dp[i][j-1]이고 dp[i][j] != dp[i-1][j]이면...
#해당 위치 i는 lcs의 문자에 포함된다.
else:
#어차피 역으로 문자열을 읽어야하므로, 배열에 미리 뒤에서부터 집어넣는다.
#인덱스가 one - based이므로... X[i]가 아니라 X[i-1]을 집어넣어야...
lcs[-k] = X[i-1]
i -= 1
j -= 1
k += 1
return ''.join(lcs)
X = input()
Y = input()
n = len(X)
m = len(Y)
#LCS의 길이를 구하는 과정
#DP[i][j]는 X[1,2,...,i]와 Y[1,2,..,j]의 가장 긴 공통 부분문자열의 길이
dp = [[0]*(m+1) for _ in range(n+1)]
#X[i] == Y[j]이면, X[1,2,..,i-1]과 Y[1,2,..,j-1]의 가장 긴 공통 부분문자열의 길이에 X[i] 하나를 더해준다
#X[i] != Y[j]이면, X[1,2,..,i]와 Y[1,2,..,j-1]의 가장 긴 공통 부분문자열의 길이와
#X[1,2,..,i-1]과 Y[1,2,..,j]의 가장 긴 공통 부분문자열의 길이 중 더 큰 값이 된다
for i in range(1,n+1):
for j in range(1,m+1):
if X[i-1] == Y[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1],dp[i-1][j]) #조건문으로 풀어쓰면 조금 더 빠르긴함..
answer = dp[n][m] #LCS의 길이
if answer == 0:
print(answer)
else:
print(answer)
print(get_lcs(dp,n,m,X))
추가로 X대신 lcs[-k] = Y[j-1]을 넣어도 당연히 맞겠지..?
def get_lcs(dp,n,m,Y):
i = n
j = m
lcs = [0]*(dp[i][j])
k = 1
while i != 0 or j != 0:
if j >= 1 and dp[i][j] == dp[i][j-1]:
j -= 1
elif dp[i][j] == dp[i-1][j]:
i -= 1
else:
lcs[-k] = Y[j-1]
i -= 1
j -= 1
k += 1
return ''.join(lcs)
또한 역추적 과정을 보면 알겠지만... 나는 지금 무조건 위로 이동하는 것부터 시작했지만..
옆으로 이동하는걸 먼저 시작해도 당연히 맞겠지??
그러니까 dp[i][j] == dp[i-1][j]를 먼저 비교하기 시작하고, 이게 다르다면 dp[i][j] == dp[i][j-1]을 먼저 비교하자
이러면 이제 i >= 1 and dp[i][j] == dp[i-1][j]를 먼저 써줘야겠지?
def get_lcs(dp,n,m,X):
i = n
j = m
lcs = [0]*(dp[i][j])
k = 1
while i != 0 or j != 0:
if i >= 1 and dp[i][j] == dp[i-1][j]:
i -= 1
elif dp[i][j] == dp[i][j-1]:
j -= 1
else:
lcs[-k] = X[i-1]
i -= 1
j -= 1
k += 1
return ''.join(lcs)
https://www.youtube.com/watch?v=z8KVLz9BFIo
https://gksrnr2305.tistory.com/2
[알고리즘] LCS(Longest Common Subsequence) 최장 공통 부분 수열 과 역추적(Trace Back) 알아보기
LCS 알고리즘 두 수열 사이에 공통적으로 존재하는 가장 긴 부분 수열을 말한다. 예를 들면 ABCDEF 와 EBDEAF 의 가장 긴 부분수열은 BDEF 이다. 설명 문자열 X[i] = {x1, x2, x3 . . .xi} , Y[j] = {y1, y2, y3 . . .yj}
gksrnr2305.tistory.com
실무에서 빠르게 LCS를 계산하는 실용적인 Hunt-Szymanski 알고리즘에 관하여 (infossm.github.io)
