Longest Common Subsequence

최장 공통 부분수열

알고리즘 구현 방법

1. LCS 2차원 배열을 생성한다.
   • 비교하는 문자열의 길이의 +1 한 값을 가로 세로에 배치한다.
2. 가로 세로 값을 비교하여 LCS 배열에 채워 넣는다.
   • 값이 같은 경우
     • L[i][j]=L[i-1][j-1]+1
   • 값이 다른 경우
     • L[i][j]=Math.max(L[i-1][j],L[i][j-1])

문제

boj9251 LCS

Reference

• https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence