LCS1

• 

  210706 동적 계획법(DP) 2- LCS ,OBST LCS ( Longest Common Subsequence) - 최장 공통 부분수열, 문자열 를 DP로 해결 LCS의 예시) 목표: 부분수열이기에 중간에 맞지 않다면 문자 사이를 건너뛰어 공통되면서 가장 긴 문자열을 찾는 것 해결법 : 를 다시 정리하면 문자열 X, 문자열 Y의 한 글자씩 비교 두 문자가 같다면 LCS[i - 1][ j - 1 ] +1 두 문자가 다르다면 LCS[i - 1][ j ] 와 LCS[ i ][ j - 1 ] 중 큰 값 표시 1 ~ 3 번 과정 반복 앞서 예로 들었던 malestrom 과 becalm 으로 과정을 보이면 한 단어를 기준으로 잡고 한 글자씩 잡고 위의 점화식대로 테이블을 채워나간다 예를 들어 b를 기준으로 잡고 m,a,l,e....m 까지 검사 이 경우 문자가 같은.. 미가공 필기(알고리즘) 2021. 7. 7.