문제
두 문자열이 주어질 때, 두 문자열의 가장 긴 공통 부분 수열(Longest Common Subsequence)의 길이를 구한다. 부분 수열은 연속하지 않아도 되지만, 원래 문자열에서의 상대적 순서는 유지해야 한다.
입력
- 첫째 줄: 첫 번째 문자열 (알파벳 대문자, 최대 1000자)
- 둘째 줄: 두 번째 문자열 (알파벳 대문자, 최대 1000자)
출력
- 두 문자열의 LCS 길이
예제
| 입력 | 출력 |
|---|---|
ACAYKP CAPCAK | 4 |
풀이
2차원 DP 테이블을 이용한 탑다운(메모이제이션 재귀) 방식으로 LCS를 계산한다.
dp[r][c]를 "A의 인덱스 r까지, B의 인덱스 c까지 중 LCS의 길이"로 정의한다.- 기저 조건: r == -1 또는 c == -1이면 0을 반환한다.
A[r] == B[c]이면:dp[r][c] = LCS(r-1, c-1) + 1A[r] != B[c]이면:dp[r][c] = max(LCS(r-1, c), LCS(r, c-1))- 코드에는 탑다운(
LCS) 방식과 바텀업(LCS2) 방식 두 가지 구현이 포함되어 있다.
핵심 아이디어: 두 문자가 같으면 이전 공통 부분에 1을 더하고, 다르면 한쪽 문자를 줄였을 때의 최댓값을 택한다. 이 점화식이 LCS 알고리즘의 핵심이다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day74BOJ9251LCS재귀반복DP공부 {
static char[] A, B;
static Integer[][] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = (A = br.readLine().toCharArray()).length;
int M = (B = br.readLine().toCharArray()).length;
dp = new Integer[N][M];
System.out.println(LCS(N - 1, M - 1));
br.close();
}
private static int LCS(int r, int c) { // 재귀 top-down
if (r == -1 || c == -1)
return 0; // 0까지 도달 후 dp인덱스 밖이 되면 0반환종료
if (dp[r][c] == null) {
dp[r][c] = 0; // 탐색 도달 시 초기화
if (A[r] == B[c])
dp[r][c] = LCS(r - 1, c - 1) + 1; // 같은 부분이 추가되어 길이 1증가
else
dp[r][c] = Math.max(LCS(r - 1, c), LCS(r, c - 1));
}
return dp[r][c];
}
private static int LCS2(int N, int M) { // 반복문 bottom-up
int[][] dp2 = new int[N + 1][M + 1];
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < M + 1; j++) {
if (A[i - 1] == B[j - 1])
dp2[i][j] = dp2[i - 1][j - 1] + 1;
else
dp2[i][j] = Math.max(dp2[i - 1][j], dp2[i][j - 1]);
}
}
return dp2[N][M];
}
}복잡도
- 시간: O(N × M) — N, M은 각 문자열의 길이 (DP 테이블 채우기)
- 공간: O(N × M) — 2차원 dp 테이블