코딩 테스트를 준비하는 것은 다소 도전적일 수 있지만, 알고리즘 문제를 체계적으로 익히면 좋은 성과를 이룰 수 있습니다.
이번 강좌에서는 최장 공통 부분 수열(LCS, Longest Common Subsequence) 문제를 다룰 것입니다.
이 문제는 문자열이나 수열에서 두 개의 서브시퀀스가 얼마나 많이 중복되는지를 측정하는 중요한 알고리즘 질문입니다.
문제 정의
두 개의 문자열이 주어졌을 때, 이 두 문자열의 최장 공통 부분 수열의 길이를 구하는 문제입니다.
두 문자열은 다음과 같습니다:
- 문자열 A: “ABCBDAB”
- 문자열 B: “BDCAB”
이 경우, 문자열 A와 B의 최장 공통 부분 수열은 “BDAB” 또는 “BCAB”이며, 이들의 길이는 4입니다.
그럼 이 문제를 해결하기 위해 동적 프로그래밍(Dynamic Programming) 기법을 사용할 것입니다.
문제 해결 전략
최장 공통 부분 수열(LCS) 문제는 재귀적 문제 해결 방식과 동적 프로그래밍을 통해 해결할 수 있습니다.
재귀적 접근 방법은 간단하지만 시간 복잡도가 매우 높아 실용적이지 않습니다. 따라서, 우리는 동적 프로그래밍을 사용할 것입니다.
1. 동적 프로그래밍 이해
동적 프로그래밍(DP)은 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 한 번만 해결하여 그 결과를 저장(caching)하는 방법입니다.
LCS 문제를 해결하기 위해 2차원 동적 배열을 사용합니다. 배열의 각 셀은 부분 문자열의 LCS 길이를 저장합니다.
2. DP 테이블 구성
두 문자열 A와 B의 길이를 각각 m, n이라고 합시다.
DP 테이블(longestCommonSubsequence 배열)은 (m + 1) x (n + 1) 크기로 구성됩니다.
여기서 DP[i][j]는 문자열 A의 첫 번째 i글자와 문자열 B의 첫 번째 j글자까지의 LCS 길이를 나타냅니다.
3. 점화식 설정
DP 테이블을 채우기 위해 다음과 같은 점화식을 사용합니다:
- 만약 A[i-1] == B[j-1]이라면,
DP[i][j] = DP[i-1][j-1] + 1 - 그렇지 않다면,
DP[i][j] = max(DP[i-1][j], DP[i][j-1])
이를 통해 두 문자열의 LCS를 계산할 수 있습니다.
C++ 구현
이제 위의 이론을 바탕으로 C++ 코드로 구현해보겠습니다.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int calculateLCS(const string &A, const string &B) {
int m = A.length();
int n = B.length();
// DP 테이블 초기화
vector<vector<int>> DP(m + 1, vector<int>(n + 1, 0));
// DP 테이블 채우기
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (A[i - 1] == B[j - 1]) {
DP[i][j] = DP[i - 1][j - 1] + 1;
} else {
DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
}
}
}
return DP[m][n];
}
int main() {
string A = "ABCBDAB";
string B = "BDCAB";
int length = calculateLCS(A, B);
cout << "최장 공통 부분 수열의 길이는 " << length << "입니다." << endl;
return 0;
}
코드 설명
위 C++ 코드에서는 calculateLCS 함수를 사용하여 두 문자열의 LCS를 계산합니다.
먼저, DP 테이블을 초기화한 후 각 문자 쌍에 대해 비교를 수행하며 DP 테이블을 채웁니다.
마지막으로 최장 공통 부분 수열의 길이는 DP 테이블의 오른쪽 아래 셀(DP[m][n])에 저장됩니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(m * n)이며, 공간 복잡도 또한 O(m * n)입니다.
이는 두 문자열의 길이에 비례하므로, 입력 문자열 길이가 길 경우 성능에 영향을 줄 수 있습니다.
결론
이번 강좌에서는 두 문자열 간의 최장 공통 부분 수열을 찾는 문제를 다루었습니다.
C++와 동적 프로그래밍을 활용하여 문제를 해결하는 방법을 알아보았으며, 최장 공통 부분 수열 문제는 코딩 테스트에서 빈번히 등장하는 문제 중 하나입니다.
다양한 문제를 통해 이와 유사한 알고리즘을 익히고 연습하신다면, 코딩 테스트에서 좋은 결과를 얻을 수 있을 것입니다.
감사합니다!