04_week_LCS 최장 공통 부분 수열

LCS : Longest Common Subsequence
최장 공통 부분 수열

같은 순서로 나타나지만 반드시 연속일 필요는 없다

ACAK 가 LCS가 된다
string 의 길이가 가장 긴 것이 최장 공통 부분 수열이된다

사용되는 곳
DNA 분석시 둘이 유사한 DNA라고 판단시 사용
등

점화식

A=[]
B=[]
for i in range():
	for j in range():
    if i==0 or j==0:
    	LSC[i][j]=0
    elif i>0 and j>0 and A[i]==B[j]:
    	LSC[i][j]=LSC[i-1][j-1]+1
    elif i>0 and j>0 and A[i]!=B[j]:
    	LSC[i][j]=max(LSC[i-1][j], LSC[i][j-1])
    else:
    	LSC[i][j]=0
        
ref : CLRS

ref : velog