백준 9252 - LCS 2

https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

먼저 dp의 3요소부터 파악해보자.

 

1) dp식

dp[i][j] : 1번 문자열의 i번째 문자, 2번 문자열의 j번째 문자까지 비교했을 때의 공통 부분 수열의 길이

예를 들어, 1번 문자열이 ACAYKP, 2번 문자열이 CAPCAK 일 경우,

 

dp[4][3]는 ACAY와 CAP를 비교했을 때의 LCS인 CA의 길이 2이다.

 

2) 초깃값

dp식의 정의에 따르면, i와 j 중 하나가 0일 경우 두 문자열 중 하나가 공백이 되므로 LCS가 반드시 0이 된다.

따라서 dp[0][j]와 dp[i][0]은 모두 0이다.

 

3) 점화식

dp[i-1][j-1]까지 계산을 마쳤다고 해보자.

 

i번 문자와 j-1번 문자가 같을 경우 dp[i][j-1]은 dp[i-1][j-1]에서 증가할 여지가 있다. 마찬가지로 dp[i-1][j]도 증가할 여지가 있다. 그리고 i번 문자와 j번 문자가 같을 경우 dp[i][j]는 확실하게 dp[i-1][j-1]에서 1 증가한다. 따라서 dp[i][j]의 값으로 고려할 수 있는 값의 종류는 3개이다.

 

dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1 (str1[i] == strb[j]일 경우)

dp[i-1][j-1]은 이 셋보다 반드시 작기 때문에 계산하지 않아도 된다.

 

만약 이해가 가지 않는다면 표를 그려 dp[i][j]를 채워보고, 귀찮다면 이 문제는 단골이고 기본형이니 위 식을 기억하자.

 

 

최대 길이는 찾았고, 이제 실제 LCS를 찾아야한다. dp문제에서 내용물 찾기는 두 단계로 구성된다.

 

먼저 dp 배열을 채우는 과정에서, dp[i][j]의 값이 확정될 때마다 그 값을 생성한 이전의 값 또는 인덱스를 표시해둔다. 이를 위해 dp배열과 동일한 크기의 path 배열을 생성해야 한다.

 

dp 배열을 모두 채웠으면, path 배열에 저장된 이전 위치 또는 값들을 바탕으로, 최종 결과값을 갖는 인덱스에서부터 역으로 돌아오며 내용물을 찾는다. 이 과정에서 스택이나 재귀호출(스택과 유사한 진행)을 사용해야 한다. 원래의 내용물을 역으로 추적하며 끝에서부터 내용물을 찾았으니, 이를 다시 뒤집어야 원본 내용물을 구할 수 있기 때문이다.

 

이를 이번 문제에 적용해보자

 

앞에서 dp[i][j]의 값이 될 수 있는 경우는 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1 3가지라고 했다. 셋 중 정해지는 값에 따라 path[i][j] 배열에 그에 맞는 표시를 작성한다. 그리고 최종 결과값이 나오는 인덱스 (len1, len2)에서부터 path[i][j]의 값을 이용해 path 배열을 역주행한다. 예를 들어 dp[4][3]에서 dp[3][3]의 값을 이용했다면 path[4][3]에는 어떻게든 이 정보가 표시되어있을 것이고, 이를 바탕으로 path[3][3]으로 이동하면 된다.

 

배열을 역주행할 때, dp[i-1][j-1] + 1이 사용되었을 경우에만 해당 문자가 실제로 출력할 LCS에 포함되므로, 이 경우만 결과 문자열에 추가한다. 앞에서는 스택을 사용해야 한다고 했지만, 이번 문제는 문자열이 내용물이기 때문에 추적 결과를 역으로 저장하기 위해 이런 방식을 사용해도 된다.

 

//res : 결과 문자열
//s[row-1] : LCS에 포함되어 res에 추가할 문자
res = s[row - 1] + res;

 

말이 너무 길었는데, dp문제는 대부분 이렇게 dp식 구성하기, 내용물을 요구할 경우 dp배열 완성 중 경로를 저장하고 이를 역추적하기 로 이루어진다. dp식 구성 방식은 천차만별이지만 내용물 역추적은 대부분 공통 형식을 가지므로 여러 dp 문제를 접해보는 편이 좋다.