Longest Common Subsequence
📢 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제
📑 어떻게 해결할까?
Dynamic Programming의 Memoization을 이용해보자!!
최장 공통 부분 수열의 길이를 memo하자!!
Q. 예를 들어 KEIOBOY와 MEIABIO의 LCS를 구해보자.
편의상 표를 만들어서 구할 거예요.
맨 앞의 0은 그냥 비워두고 (채워도 상관없어요) Index 하나당 KEIOBOY를 한글자씩 넣겠습니다.
비교 방식은 각 문자열의 첫 문자부터 하나씩 길이를 늘여가면서 비교해볼 거예요.
먼저 K (KEIOBOY)와 M (MEIABIO)을 비교했을 때 다르다는 걸 알 수 있어요. 고로 아래와 같이 memo[1][1]에 최장 공통 부분 문자열의 길이 0을 넣어요.
위에서 말했다시피 KEIOBOY의 K부터 하나씩 늘여가면서 비교해봐요. 공통 부분 문자열이 없으므로 memo[1][1] ~ memo[1][7]에는 0을 넣어요.
다음으로 KE (KEIOBOY)와 ME (MEIABIO)를 비교했을 때 E라는 공통 문자열이 존재해요. memo[2][2]에 공통 문자열의 길이인 1을 넣어요.
KEIOBOY를 하나씩 늘여가며 ME와 비교했을 때 최대 공통 문자열의 길이가 1인 것을 알 수 있어요. memo[2][2] ~ memo[2][7]에는 1을 넣어요.
다음으로 MEI와 KEIOBOY를 비교할 차례예요.
MEI와 KE는 E라는 공통 문자열이 존재하므로 memo[3][2]에는 1을 넣어요.
MEI와 KEI는 EI라는 문자열이 공통으로 존재하기 때문에 memo[3][3]에 2를 넣어요.
더는 공통되는 문자열이 없으므로 memp[3][3] ~ memo[3][7]에 2를 넣어요.
위의 표를 보면
firstString = "KEIOBOY", secondString = "MEIABOY" 일 때
if(firstString[i] == secondString[j])
memo[i][j] = memo[i - 1][j - 1] + 1
else
memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])
이라는 규칙을 발견할 수 있어요.
위의 규칙을 적용하여 표에 나타내보면
KEIOBOY와 MEIABIO의 Longest Common Subsequence는 4라는 것을 알 수 있어요.
위의 규칙을 적용한 코드는 아래에서 확인해주세요!!!
백준 9251 - LCS
백준 9251 - 해답
