반응형
문자열 동적 계획법
문자열 관련 문제는 많은 응용 분야에서 중요합니다. 오늘은 두 가지 주요 문제인 편집 거리(Edit Distance)와 최장 공통 부분 수열(Longest Common Subsequence, LCS)에 대해 학습하겠습니다.
편집 거리 (Edit Distance)
편집 거리(Edit Distance)는 두 문자열을 같게 만들기 위해 필요한 최소 편집 연산 횟수를 의미합니다. 가능한 편집 연산은 삽입, 삭제, 교체입니다.
문제 정의
두 문자열 ( s1 )과 ( s2 )가 주어졌을 때, ( s1 )을 ( s2 )로 변환하는 데 필요한 최소 편집 연산 횟수를 계산합니다.
편집 거리 구현
다음은 C++로 편집 거리 문제를 해결하는 예제입니다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
// 편집 거리 계산 함수
int editDistance(const std::string& s1, const std::string& s2) {
int m = s1.size();
int n = s2.size();
// DP 테이블 초기화
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// 초기 값 설정
for (int i = 0; i <= m; ++i) {
dp[i][0] = i;
}
for (int j = 0; j <= n; ++j) {
dp[0][j] = j;
}
// DP 점화식 적용
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = std::min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1});
}
}
}
return dp[m][n];
}
int main() {
std::string s1, s2;
std::cout << "첫 번째 문자열을 입력하세요: ";
std::cin >> s1;
std::cout << "두 번째 문자열을 입력하세요: ";
std::cin >> s2;
int result = editDistance(s1, s2);
std::cout << "편집 거리: " << result << std::endl;
return 0;
}
최장 공통 부분 수열 (Longest Common Subsequence, LCS)
최장 공통 부분 수열(LCS)은 두 문자열에서 순서를 유지하면서 공통적으로 나타나는 가장 긴 부분 수열을 찾는 문제입니다.
문제 정의
두 문자열 ( s1 )과 ( s2 )가 주어졌을 때, 두 문자열의 최장 공통 부분 수열의 길이를 계산합니다.
최장 공통 부분 수열 구현
다음은 C++로 최장 공통 부분 수열 문제를 해결하는 예제입니다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
// LCS 길이 계산 함수
int longestCommonSubsequence(const std::string& s1, const std::string& s2) {
int m = s1.size();
int n = s2.size();
// DP 테이블 초기화
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// DP 점화식 적용
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
int main() {
std::string s1, s2;
std::cout << "첫 번째 문자열을 입력하세요: ";
std::cin >> s1;
std::cout << "두 번째 문자열을 입력하세요: ";
std::cin >> s2;
int result = longestCommonSubsequence(s1, s2);
std::cout << "최장 공통 부분 수열의 길이: " << result << std::endl;
return 0;
}
설명
- 편집 거리:
editDistance함수는 두 문자열 간의 편집 거리를 계산합니다.dp[i][j]는 첫 번째 문자열의 처음 (i) 문자와 두 번째 문자열의 처음 (j) 문자의 편집 거리를 나타냅니다.- 초기 값은 한 문자열이 비어 있는 경우, 다른 문자열의 길이만큼 편집이 필요합니다.
- 점화식: 문자가 같은 경우 편집이 필요 없고, 다른 경우 삽입, 삭제, 교체 중 최소 비용을 선택합니다.
- 최장 공통 부분 수열:
longestCommonSubsequence함수는 두 문자열 간의 최장 공통 부분 수열의 길이를 계산합니다.dp[i][j]는 첫 번째 문자열의 처음 (i) 문자와 두 번째 문자열의 처음 (j) 문자의 최장 공통 부분 수열의 길이를 나타냅니다.- 초기 값은 한 문자열이 비어 있는 경우, 공통 부분 수열은 0입니다.
- 점화식: 문자가 같은 경우 현재 문자를 공통 부분 수열에 포함하고, 다른 경우 이전 값 중 최대값을 선택합니다.
문자열 동적 계획법의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 22: 고급 정렬 알고리즘(TimSort, IntroSort)"에 대해 학습하겠습니다.
반응형