가장 긴 공통 부분 문자열

제코베 JS 100제 / 77 / 가장 긴 공통 부분 문자열

가장 긴 공통 부분 문자열(Longest Common Subsequence)이란 A, B 두 문자열이 주어졌을 때 두 문자열에 공통으로 들어 있는 요소로 만들 수 있는 가장 긴 부분문자열을 말합니다. 여기서 부분문자열이란 다른 문자열에서 몇몇의 문자가 빠져 있어도 순서가 바뀌지 않은 열을 말합니다. 예를 들어 S1 = ['T', 'H', 'I', 'S', 'I', 'S', 'S', 'T', 'R', 'I', 'N', 'G', 'S'] S2 = ['T', 'H', 'I', 'S', 'I', 'S']라는 두 문자열이 있을 때 둘 사이의 부분 공통 문자열의 길이는 ['T', 'H', 'I', 'S', 'I', 'S']의 6개가 됩니다. 이처럼 두 문자열이 주어지면 가장 긴 부분 공통 문자열의 길이를 반환하는 ..