[BOJ] 9251 - LCS

문제 출처

백준 9251 - LCS

 

풀이

LCS(Longest Common Subsequence) 알고리즘을 사용하여 최장 공통 부분 문자열을 구하는 문제였습니다.

 

주어진 문자열의 공통 부분 문자열 중 그 길이가 최장인 것을 LCS라 말하는데 이 때 Substring과 Subsequence의 개념이 다릅니다.

 

Substring은 연속된 부분 문자열이고 Subsequence는 연속되지 않은 부분 문자열입니다.

 

즉, 연속되지 않은 부분 문자열의 길이가 최장인 것입니다.

 

LCS 알고리즘을 사용하여 길이를 구하면 풀 수 있는 문제입니다.

 

코드

small-j/BOJ_Algorithm