문제 설명
주어진 두 문자열 A와 B가 있을 때, 이들 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS)을 찾는 문제입니다. 부분 수열은 문자열에서 문자의 순서를 유지하면서 삭제로 얻을 수 있는 문자열입니다. 즉, A의 부분 수열이 B에 존재해야 합니다.
예를 들어, 문자열 A가 “ABCBDAB”이고 B가 “BDCAB”라면, 최장 공통 부분 수열은 “BCAB”입니다. 이러한 LCS 문제는 다양한 분야에서 효율적인 알고리즘을 필요로 하는 문제입니다.
문제 입력
두 문자열 A와 B의 길이 N, M (1 ≤ N, M ≤ 1000) 및 문자열 A와 B가 주어집니다.
문제 출력
최장 공통 부분 수열의 길이를 출력합니다.
문제 해결 과정
1. 동적 프로그래밍 이해
이 문제는 동적 프로그래밍(DP)을 사용하여 해결할 수 있습니다. DP는 복잡한 문제를 작은 부분 문제로 나누어 해결하여 효율성을 높이는 기법입니다. 이 경우, DP 배열을 사용하여 각 문자 쌍 간의 LCS 길이를 저장하고 계산합니다.
2. DP 배열 초기화
우선, 두 문자열 A와 B의 길이에 따라 2차원 DP 배열을 초기화합니다. DP[i][j]는 A의 첫 i개 문자와 B의 첫 j개 문자의 최장 공통 부분 수열의 길이를 나타냅니다.
int[,] dp = new int[N + 1, M + 1];
3. DP 상태 전이
DP 규칙은 다음과 같습니다:
- 만약 A의 i번째 문자와 B의 j번째 문자가 같으면:
dp[i][j] = dp[i - 1][j - 1] + 1 - 만약 A의 i번째 문자와 B의 j번째 문자가 다르면:
dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1])
4. 최종 결과
DP 배열이 채워진 후, dp[N][M]에는 최장 공통 부분 수열의 길이가 저장됩니다.
코드 구현
using System;
class Program
{
static void Main(string[] args)
{
string A = "ABCBDAB";
string B = "BDCAB";
int N = A.Length;
int M = B.Length;
int[,] dp = new int[N + 1, M + 1];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
if (A[i - 1] == B[j - 1])
{
dp[i, j] = dp[i - 1, j - 1] + 1;
}
else
{
dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
}
}
}
Console.WriteLine("최장 공통 부분 수열의 길이: " + dp[N, M]);
}
}
테스트 케이스
예제 입력
A: ABCBDAB
B: BDCAB
예제 출력
최장 공통 부분 수열의 길이: 4
시간 복잡도 분석
이 동적 프로그래밍 알고리즘의 시간 복잡도는 O(N * M)이며, 공간 복잡도 또한 O(N * M)입니다. 이를 통해 두 문자열의 길이가 1000일 때도 충분히 성능을 만족하는 알고리즘입니다.
결론
최장 공통 부분 수열(LCS) 문제는 컴퓨터 과학의 여러 분야에서 어떻게 알 수 있는지를 보여주는 주요 문제입니다. 동적 프로그래밍을 사용하여 효율적으로 해결할 수 있음을 확인했습니다. 이 방법은 실제 코딩테스트에서 수시로 등장하므로, 잘 이해하고 연습하는 것이 중요합니다.