1. 동적 계획법이란?
동적 계획법(Dynamic Programming, DP)은 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 기법입니다. 일반적으로 재귀적 접근 방식을 사용하되, 하위 문제의 결과를 저장하여 중복 계산을 줄이는 것이 특징입니다.
DP는 주로 최적화 문제에 효과적이며, 두 가지 주요 개념인 ‘메모이제이션(memoization)’과 ‘타뷸레이션(tabulation)’으로 나누어집니다.
2. 문제 설명
2.1 문제: 최장 공통 부분 수열 (Longest Common Subsequence, LCS)
두 문자열 A와 B가 주어졌을 때, A와 B의 최장 공통 부분 수열의 길이를 구하는 문제입니다. 부분 수열은 A와 B에서 일부 문자를 그대로 유지하면서 순서를 변경하지 않고 선택할 수 있는 문자들의 집합입니다.
2.2 입력 예시
A: "ABCBDAB"
B: "BDCAB"
2.3 출력 예시
"LCS의 길이는 4입니다." // "BCAB" 또는 "BDAB"
3. 문제 해결 과정
3.1 문제 분석
문제를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:
- 문자열 A와 B의 길이를 각각 n과 m으로 정의합니다.
- 2차원 배열 dp를 생성하여 dp[i][j]가 A의 i번째 문자까지의 LCS와 B의 j번째 문자까지의 LCS 길이를 저장하도록 합니다.
- 문자열이 일치할 경우, dp[i][j] = dp[i-1][j-1] + 1; 그렇지 않을 경우 dp[i][j] = max(dp[i-1][j], dp[i][j-1])로 설정합니다.
3.2 상태 전이 관계
동적 계획법에서의 상태 전이는 다음과 같이 정의할 수 있습니다:
dp[i][j] =
{
dp[i-1][j-1] + 1, if A[i-1] == B[j-1]
max(dp[i-1][j], dp[i][j-1]), if A[i-1] != B[j-1]
}
3.3 자바 구현 코드
이제 자바로 LCS를 구현해보겠습니다.
public class LCS {
public static int longestCommonSubsequence(String A, String B) {
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.charAt(i - 1) == B.charAt(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]);
}
}
}
return dp[n][m];
}
public static void main(String[] args) {
String A = "ABCBDAB";
String B = "BDCAB";
int length = longestCommonSubsequence(A, B);
System.out.println("LCS의 길이는 " + length + "입니다.");
}
}
4. 전체 시간 복잡도와 공간 복잡도
이 알고리즘의 시간 복잡도는 O(n * m)이며, 공간 복잡도는 O(n * m)입니다. 하지만 공간 최적화를 통해 O(min(n, m))으로 줄일 수도 있습니다.
5. 추가 풀이 및 예제
이 문제를 확장하여 해결할 수 있는 여러 다른 문제나 변형 문제들을 살펴보겠습니다. 예를 들어, 주어진 문자열들의 최장 공통 부분 수열을 구한 다음, 해당 문자열을 출력하는 함수도 추가할 수 있습니다.
6. 최종 정리
동적 계획법은 복잡한 문제를 하위 문제로 나눠 해결할 수 있는 매우 유용한 기법입니다. LCS 문제를 통해 DP의 기본 개념을 이해했다면, 자신만의 다른 문제를 풀어보면서 연습하는 것이 좋습니다.
7. 다음 강좌 안내
다음 강좌에서는 동적 계획법의 다른 예제를 다루고, 다양한 최적화 기법에 대해 알아볼 예정입니다. 관심이 있으시다면 많은 참여 부탁드립니다!