백준 9251: LCS ( 최장 공통 부분수열 {DP} / Swift )

두 개의 부분수열이 주어졌을 때, 가장 긴 공통 부분 수열을 구해야하는 문제이다.

ACAYKP와  CAPCAK가 주어진다면

 

ACAYKP

CAPCAK

 

ACAK라는 부분 수열이 있기에 답은 4가 된다.

 

Point 1:

arr[i][j]가 나타내는 것은, a문자열의 i번째 요소를 b문자열의 j번째 요소까지 비교하였을 때 최장 공통 부분수열의 길이이다.

 

Point 2:

arr[i][j] = arr[i - 1][j - 1] + 1이다.  

예를 들면, ACCC와 같이 b문자열이 진행되고, 현재 a문자열에서 C문자를 체크하고 있을 때, C가 나올 때마다 1씩 증가시키는 것은 말이 되지 않는다.

1 222와 같이 진행되는 것이 맞다.

 

Point 3:

arr[i - 1]과 b[j - 1]이 일치하지 않는 경우,

 arr[i][j] = max( arr[i - 1][j], arr[i][j -1])인 이유는, arr[i -1][j]는 이미 이전 문자까지 체크했을 때 구해놓았던 최장 공통 부분수열 값이고, arr[i][j - 1]은  현재의 문자를 체크하며 앞쪽에서 업데이트 해주었다면, 뒷쪽으로도 연결시켜주어야하기 때문이다.

 

Point 2: