[백준][python]9251 LCS
문제
https://www.acmicpc.net/problem/9251
소스코드
import sys
input = sys.stdin.readline
if __name__ == "__main__":
a = '0' + input().rstrip() #마진 주기
b = '0' +input().rstrip() #마진 주기
#각 문자열의 길이 찾기
len_a = len(a)
len_b = len(b)
#dp 저장소
lcs = [[0] * (len_b) for _ in range(len_a)]
#lcs 길이 탐구
for i in range(1,len_a):
for j in range(1,len_b):
if a[i] == b[j]:#문자가 같은 경우, 바로 위 대각선 lcs 값에 + 1
lcs[i][j] = lcs[i-1][j-1] + 1
else: #같지 않은 경우 위쪽의 최댓값과 왼쪽의 최댓값중 큰 값
lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1])
print(lcs[len_a-1][len_b-1]) #이 문제의 답
#LCS 찾기 -- 이건 문제는 아닌데 공부용
res = ""
i = len_a-1
b = len_b-1
while 1:
if lcs[i][j] == 0:
break #lcs 값이 0 이 나오면 종료 더이상 없다는거
#위나 왼쪽과 같은 값이 있다 -> 같지 않은 값
if lcs[i][j] == lcs[i-1][j]:
i = i-1
elif lcs[i][j] == lcs[i][j-1]:
j = j-1
#위나 왼쪽에 같은 값이 없다?대각선 위로 올라가고 그 값이 공통 값이므로 추가해주기
else:
res += a[i]
i = i-1
j = j-1
print(res[::-1])설명
Longest Common Subsequence ( 최장 공통 부분 수열)은 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
특이점은 연속적이지 않아도 된다는 점이다. 문제에서 주어진 ACAYKP와 CAPCAK의 LCS는 ACAK이다.
DP 를 이용해서 메모이제이션 해야할 값은 특정 순서의 문자열에서 현재까지 누적된 같은 문자의 갯수이다.
LCS 라는 이차원 배열을 사용하여 행은 첫번째 문자열의 비교했을 때 누적값, 열은 두번째 문자열을 비교했을 때 누적값으로 생각해보자
1. 만약에 두 문자열이 같다면 LCS[i][j] = LCS[i-1][j-1] + 1 :그전까지의 문자열에서 같은 문자 한개가 더 추가된다.
2. 두 문자열이 다르다면 내 차례 이전에 비교한 값중에 큰 값을 선택한다. LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1)
그림으로 나타내면 아래와 같다. 이 그림을 예시로 경우를 설명해보겠다.
1. 문자열이 같은 경우
AC 와 CAPC 가 같은 경우는 AC 로 2 라고 확인할 수 있다. 이는
그 전 (i-1,j-1) 까지 비교한 값에 현재 값 C를 추가했는대 동일하다라는 뜻이다.
(i-1, j-1) 은 CAP 와 A를 비교한 값이고 1이다.
2. 문자열이 다른 경우
ACA 와 CAP 를 비교하면 마지막 문자열이 다르고 CA가 같아서 2라고 확인할 수 있다. 그 전까지 확인 한 값중에서 큰 값을 넣는다. (현재 값 제외하고 지금까지 누적된 값중 가장 큰 값)
