[백준] 9251 : LCS (최장 공통 부분 수열)

url: https://www.acmicpc.net/problem/9251

9251번: LCS

 

LCS = 최장 공통 부분 수열

두 문자열에서 연속적이지 않으면서 한방향(동일한 순서)로 가장 긴 공통 문자열을 찾는 문제이다.

DP 유형의 고전적인 문제(유형화된 문제)라고 할 수 있다.

 

점화식

인덱스가 각각 0~i, 0~j라고 할 때, dp 배열을 채워보자.

직전 문자 (각각 i-1 위치 문자와 j-1 위치 문자)가 같다면, i와 j위치 문자의 경우의 수는 직전 LCS 문자열 크기 +1이다.

직전 문자가 다르다면, 직전 문자열들에서 새로운 값까지 포함하여 비교해서 더 큰 값을 찾아 반환한다.

 

for(int i=1;i<=a.size();i++){ 
    for(int j=1;j<=b.size();j++){
        if(a[i-1]==b[j-1]){
            dp[i][j] = dp[i-1][j-1] + 1;
        }
        else{
            dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

반복문에서 i와 j는 1부터 각각의 문자열 크기까지의 범위이다.

(일반적으로는 0부터 문자열 크기-1까지이다.)

 

이는 i,j가 1일때 첫번째 원소(인덱스 0인 원소)를 비교하고,

이는 i,j가 2일때 두번째 원소(인덱스 1인 원소)를 비교하며,

i,j가 각각의 문자열 길이여야 마지막 글자(인덱스 a.size()-1 과 b.size()-1)까지 비교할 수 있다.

=> 반복문의 i,j가 실제 위치(1부터 시작)을 가리킨다.

 

잘 이해가 안되어 내일 추가정리할 예정입니다.