문제 링크 : https://www.acmicpc.net/problem/9251
코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!
문제 정의
LCS란?
보통 LCS라 하면 두 가지 정의가 있습니다.
이 문제에서는
최장 공통 부분 수열의 문자열을 구해야 합니다.
접근 방법
크게 두 가지입니다.
- LCS 길이 계산을 위한 DP 테이블 구성해서 LCS 길이 구하기
- DP 테이블을 이용한 LCS 복원(역추적)으로 LCS 문자열 구하기
1-based DP
저는 1-based DP를 구현했습니다.
0-based DP를 구현한다면 첫 행을 DP 테이블에 채울 시
별도의 인바운드 로직을 처리해야되기 때문에
조금의 메모리 사용과 trade-off 해서 코드의 간결성을 살렸습니다.
점화식
DP 문제를 풀 때 가장 핵심은
점화식을 세우는 것입니다.
점화식을 세우기 전에 어떻게 행동해야하는지 확인해보겠습니다.
- 문자열1, 문자열2의 한글자씩 비교
- 두 문자가 같다면 dp[i-1][j-1] 값을 찾아 +1
- 두 문자가 다르다면 dp[i-1][j]와 dp[i][j-1] 중에 큰 값을 표시
- 위 과정을 반복합니다.
제가 세운 점화식은 다음과 같습니다.
이걸 코드화 시키면 다음과 같습니다.
의사 코드
if (str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1] + 1;
else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}실제 코드
점화식을 보고 의사 코드를 작성했는데
문자열 접근이 틀린 것을 제외하면 로직 자체는 일치하는 것을 볼 수 있습니다.
dp[i–1][j]와 dp[i][j-1]는 어떤 의미인가?
주황색 부분은 문자열 AB와 GBC의 LCS 길이를 저장해야 합니다.
만약 두 문자열의 마지막 문자열을 비교했는데 아쉽게도 다른 문자입니다.
그럴 때 노란 부분인 dp[i-1][j]와 dp[i][j-1]에서 최댓값을 가져오게 됩니다.
그렇다면
dp[i-1][j]와dp[i][j-1]은 무엇을 의미할까요
dp[i][j]에서 i는 str1의 길이를 의미합니다.
문자열1이 GBCDFE이고 i가 3인 경우
문자열1에서 앞에서부터 길이3을 자른 GBC가 dp[i][j]의 i입니다.
그러면 j는
문자열2이 ABCDEF이고 j가 3인 경우
문자열2에서 앞에서부터 길이3을 자른 ABC가 dp[i][j]의 j입니다.
즉 dp[i–1][j]와 dp[i][j-1]는
최대 갱신 값이 없으니 이전 문자열에서 LCS 최댓값을 dp[i][j]의 최댓값으로 하겠다
라는 의미입니다.
dp[i-1][j-1]는 어떤 의미인가?
이 값을 가져오는 경우는 하나입니다.
문자열 1의 i번째 문자와
문자열 2의 j번째 문자가 일치하는 경우입니다.
예를 들어 ABC와 GBC를 비교한다고 가정했을 때
마지막 문자열인 C가 일치합니다.
그러면 최댓값 갱신이 일어나므로
둘 다 이전 문자열인 AB와 GB에서 1증가한 값이 dp[i][j]에 저장되게 됩니다.
DP 테이블 채우기 예시
저희가 LCS를 채울 때 비교하는 두 끝 문자열이 같으면
dp[i-1][j-1]에서 1 증가시킨 값을 dp[i][j]에 대입했습니다.
이걸 역으로 하면 LCS 문자열을 찾을 수 있습니다.
문자열의 끝에서부터 시작해서
- 왼쪽 또는 위가 현재 LCS 값과 같다면 해당 위치로 이동
- 두 문자열의 맨 끝 문자가 같지 않거나
- 두 문자열의 맨 끝 문자가 같아도 LCS가 아닌 값이라는 의미
- 위의 경우가 아닌 경우는 맨 끝 두 문자가 LCS의 부분 문자이므로
LCS 문자열에 해당 문자를 추가하고 좌상단으로 대각 이동
역추적 예시 내용은 PPT로 작성한 내용이 있어 그림으로 대체하겠습니다.
DP 테이블 역추적
저희는 문자열 1과 문자열 2의 LCS 길이는 알지만
어떤 문자열인지는 알지 못합니다.
DP 테이블을 활용한 역추적을 통해서 LCS 문자열을 구할 수 있습니다.
위와 같은 플로우로 정답을 찾을 수 있게 됩니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = " " + br.readLine();
String str2 = " " + br.readLine();
String answer = "";
int N = str1.length() - 1;
int M = str2.length() - 1;
int[][] dp = new int[N+1][M+1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (str1.charAt(i) == str2.charAt(j)) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
traceLCS(N, M, dp, str1);
}
static void traceLCS(int y, int x, int[][] dp, String str) {
StringBuilder sb = new StringBuilder();
while (y > 0 && x > 0) {
if (dp[y][x] == dp[y][x-1]) {
x--;
}
else if (dp[y][x] == dp[y-1][x]) {
y--;
}
else {
sb.append(str.charAt(y));
x--;
y--;
}
}
System.out.println(sb.length());
System.out.println(sb.reverse());
}
}
