목록알고리즘 (1)

이 험난한 세상에서어어~

LCS(Longest Common Subsequence, 최장 공통 부분 수열) java

LCS란? 부분 수열 LCS는 최장 공통 부분 수열로 두 개의 수열이 주어졌을 때, 공통 수열 중 제일 긴 것을 의미한다. 예를 들어서 abcf와 aebwcd가 있다고 생각해 보자. 그렇다면 여기서 나오는 LCS는 abc이다. abcf aebwcd 위의 굵게 표시된 문자들을 보면 알 수 있을 텐데, 공통 부분 수열은 굳이 문자들의 한 번에 이어질 필요가 없다. 공통된 문자가 얼마나 길게 차례대로 나오느냐를 따지는 문제이기 때문이다. 최장 공통 부분 수열 이제 최장 공통 부분 수열을 구하는 방법을 알아보자. 그러기 전에 아래의 유튜브 비디오를 보고 오는 것을 추천한다. 현재 글도 아래 동영상을 기반으로 작성한 것이다. https://www.youtube.com/watch?v=sSno9rV8Rhg LCS의 ..
algorithm/유형 2023. 7. 29. 00:14
이전 Prev 1 Next 다음