문자열과 시퀀스에 대한 동적 계획법
- 이전 게시물에서 다룬 문제는 정수 시퀀스 계산 문제에 초점을 두었다.
- 이번에는 동적 계획법이 많이 사용되는 분야 중의 하나인 데이터 시퀀스의 패턴 문제에 대해 알아본다.
- 주로 문자열 검색, 비교, 문자열 재구성 등의 문제와 관련이 있다.
EX) 버전 관리 시스템(VCS)
- Git과 같은 VCS에서 우리가 다룰 데이터 시퀀스의 패턴 문제가 적용된다
- VCS는 변경된 소스 코드 부분을 쉽게 찾아보기 위해 두 가지 버전의 소스 코드를 비교하여 사용자에게 차이점을 표시해주는 비교 기능을 제공한다
- 두 버전에 공통적인 문자열 시퀀스가 연속적일 필요가 없다는 사실을 고려하여 두 소스 코드의 유사성을 판별해야 한다.
- 문자열 일부가 제거되거나 새로운 문자열이 임의 위치에 추가될 수도 있다.
- 이러한 작업은 근사 문자열 매칭(approximate string matching) 또는 퍼지 문자열 매칭(fuzzy string matching)이 필요하며, 이를 위해 동적 계획법이 사용된다.
최장 공통 부분 시퀀스 문제(LCS, Longest Common Subsequence)
- 최장 공통 부분 시퀀스 문제는 동적 계획법의 유명한 예제 중 하나이다.
두 개의 데이터 시퀀스가 주어질 때,
두 시퀀스에 공통적으로 나타나는 가장 긴 부분 시퀀스는 무엇인가?- ex)
- A = "ALBOCNDGZEYSXTW"
- B = "12L45O78N90GE9876S5432T"
- LCS = "LONGEST"
- 먼저 기저 조건부터 시작하여 문제 구조를 수식으로 표현해보자
- (1) A 또는 B가 빈 문자열인 경우
- 최장 공통 부분 시퀀스의 길이는 0
- (2) A와 B가 모두 하나의 문자로 구성된 경우
- (3) A는 하나의 문자이고, B는 두 문자로 구성된 경우
- (2)와 (3) 경우 공통 문자가 하나 있거나, 또는 하나도 없는 경우가 존재한다.
- (4) A와 B가 모두 두 문자로 구성된 경우
- 두 문자열이 완전히 같거나, 한 문자만 같거나, 또는 공통 문자가 전혀 없는 경우가 존재한다.
- (1) A 또는 B가 빈 문자열인 경우
- (1) -> (4) 문제를 보면 LCS 문제가 중복되는 부분 문제를 포함하고 있다는 사실을 알 수 있다.
- DP로 해결하는 것이 효율적!
전수 조사 방식으로 해결해보기
- 두 시퀀스의 부분집합을 비교하여 처리해나가야 한다.
- 몇 가지 고려해야할 사항
- 공통 부분 문자 시퀀스는 문자열 전체에서 다양한 형태의 배치에 의해 여러 번 나타날 수 있다.
- 특정 위치에서 시작하는 공통 부분 시퀀스가 여러 개 존재할 수 있다.
- 필요한 것
- 문자열 A와 B의 특정 문자 위치를 가리키는 두 개의 인덱스 i와 j가 필요하다.
- 지금까지 찾은 공통 부분 시퀀스(문자열)도 저장하고 있어야 한다.
만약 i가 A의 길이보다 커지거나 또는 j가 B의 길이보다 커지면:
- 재귀를 종료하고, 부분 시퀀스의 길이를 반환한다
만약 A[i] = B[i]이면:
- 부분 시퀀스 길이를 1만큼 증가시킨다
- i와 j를 각각 1씩 증가시킨다
그렇지 않으면:
- 옵션 1) (i + 1)번째와 j번째 문자에 대해 검사를 진행한다.
- 옵션 2) i번째와 (j + 1)번째 문자에 대해 검사를 진행한다.
이 상태의 LCS는 옵션 1 및 옵션 2의 최댓값과 같다.- 두 문자열의 인덱스 i와 j를 동시에 증가시키는 경우는 따로 고려하지 않는다.
- 어차피 옵션 1과 2에 의해 추후에 만나게 되기 때문
- 부분 문제 트리를 통해서, 아직 명확하진 않지만 최적 부분 구조에 대한 기본적인 일반화를 해보자
- 같은 길이의 부분집합만 비교하면 된다
- 특정 상태에서 다음 상태로 전이되기 위해서는 i 또는 j가 증가되거나, 또는 i와 j가 같이 증가해야 한다.
- 두 문자열 중 어느 하나라도 맨 마지막에 도달하면 탐색이 끝난다.
- 같은 길이의 부분집합만 비교하면 된다
vector<vector<pair<int, int>>> found;
int LCS_BruteForce(string A, string B, int i, int j,
vector<pair<int, int>> subsequence)
{
// 만약 i가 A의 길이보다 커지거나 또는 j가 B의 길이보다 커지면:
if (i >= A.size() || j >= B.size())
{
found.push_back(subsequence);
// 재귀를 종료하고 부분 시퀀스의 길이를 반환합니다.
return subsequence.size();
}
// 만약 A[i] = B[j] 이면:
if (A[i] == B[j])
{
// 부분 시퀀스 길이를 1만큼 증가합니다.
subsequence.push_back({i, j});
// i와 j를 각각 1씩 증가합니다.
return LCS_BruteForce(A, B, i + 1, j + 1, subsequence);
}
/* 그렇지 않으면:
옵션 1) (i + 1)번째와 j번째 문자에 대해 검사를 진행합니다.
옵션 2) i번째와 (j + 1)번째 문자에 대해 검사를 진행합니다.
이 상태의 LCS는 옵션 1 및 옵션 2의 최댓값과 같습니다.
*/
return max(LCS_BruteForce(A, B, i + 1, j, subsequence),
LCS_BruteForce(A, B, i, j + 1, subsequence));
}최적화 첫 단계: 최적 부분 구조 찾기
- 앞서 살펴본 로직을 최적화해보자
- 두 개의 문자열 중 하나라도 비어 있는 상태이면 LCS 값은 0이다.
- A = "ABCX", B = "ACYXB" 인 경우
- LCS(A, B, 0, 0) = 1 + LCS(A, B, 1, 1) 이 성립한다.
- 이를 앞에서 부터 접근하지 말고 뒤에서 부터 접근해보자
만약 두 문자열 중 하나라도 빈 문자열이라면:
LCS = 0
그렇지 않으면:
A의 부분 문자열과 B의 부분 문자열 마지막 문자가 같으면:
A와 B의 부분 문자열에서 구한 LCS 길이는 각 부분 문자열에서
마지막 한 문자를 제외한 문자열로부터 구한 LCS 길이에 1을 더한 것과 같다.
그렇지 않으면:
LCS 길이는 다음 두 경우의 최댓값과 같다:
1) A의 부분 문자열에서 마지막 문자를 제외한 것과
B의 부분 문자열에서 구한 LCS 길이
2) B의 부분 문자열에서 마지막 문자를 제외한 것과
A의 부분 문자열에서 구한 LCS 길이- 메모이제이션을 통해 모든 단계의 결과를 2차원 벡터에 저장할 수 있다.
- 이 때, 첫 번째 차원의 크기는 A 문자열 길이와 같고, 두 번째 차원의 크기는 B 문자열 길이와 같다.
- 기저 조건을 제외하고, memo[i - 1][j - 1] 위치에 이미 계산된 결과가 저장되어 있는지 확인하여 저장되어 있지 않다면 앞에서 정의한 로직을 이용하여 재귀적으로 값을 계산하여 캐시(여기선 벡터)에 저장한다.
메모이제이션으로 LCS 찾기
const int UNKNOWN = -1;
int LCS_Memoization(string A, string B, int i, int j,
vector<vector<int>>& memo)
{
// 기저 조건 - 빈 문자열에 대해서는 0을 반환
if (i == 0 || j == 0)
{
return 0;
}
// 두 문자열의 부분 문자열에 대해 결과가 저장되어 있으면 반환
// Have we found a result for the prefixes of the two strings?
if (memo[i - 1][j - 1] != UNKNOWN)
{
return memo[i - 1][j - 1];
}
// A와 B의 두 부분 문자열에서 맨 마지막 문자가 같은지 확인
if (A[i - 1] == B[j - 1])
{
// 이 경우 A와 B의 부분 문자열에서 구한 LCS 길이는 각 부분 문자열에서
// 마지막 한 문자를 제외한 문자열로부터 구한 LCS 길이에 1을 더한 것과 같음
memo[i - 1][j - 1] = 1 + LCS_Memoization(A, B, i - 1, j - 1, memo);
// 테이블에 저장된 결과를 반환
return memo[i - 1][j - 1];
}
// A와 B의 두 부분 문자열에서 맨 마지막 문자가 같지 않다면
// A의 부분 문자열에서 마지막 문자를 제외한 것과 B의 부분 문자열에서 구한 LCS 길이,
// B의 부분 문자열에서 마지막 문자를 제외한 것과 A의 부분 문자열에서 구한 LCS 길이 중
// 최댓값을 선택하여 지정
memo[i - 1][j - 1] = max(LCS_Memoization(A, B, i - 1, j, memo),
LCS_Memoization(A, B, i, j - 1, memo));
return memo[i - 1][j - 1];
}하향식에서 상향식으로: 메모이제이션에서 타뷸레이션 방식으로 바꾸기
- 메모이제이션으로 저장한 테이블을 출력하면 다음과 같은 패턴을 확인할 수 있다.
- 문자가 서로 같은 행과 열에서는 memo[i][j] = memo[i - 1][j - 1] + 1;
- 문자가 서로 같지 않은 행과 열에서는 memo[i][j] = memo[i - 1][j], memo[i][j - 1]중 최댓값
- 위 패턴을 통해 단순히 상향식으로 바꿔줄 수 있다.
만약 i = 0 또는 j = 0(빈 부분 문자열):
LCS(i, j) = 0
그렇지 않으면:
만약 두 부분 문자열의 마지막 문자가 같다면:
LCS(i, j) = LCS(i - 1, j - 1) + 1
그렇지 않으면:
LCS(i, j) = max(LCS(i - 1, j), LCS(i, j - 1))string ReconstructLCS(vector<vector<int>> DP, string A, string B, int i, int j)
{
if (i == 0 || j == 0)
{
return "";
}
if (A[i - 1] == B[j - 1])
{
return ReconstructLCS(DP, A, B, i - 1, j - 1) + A[i - 1];
}
else if (DP[i - 1][j] > DP[i][j - 1])
{
return ReconstructLCS(DP, A, B, i - 1, j);
}
else
{
return ReconstructLCS(DP, A, B, i, j - 1);
}
}
string LCS_Tabulation(string A, string B)
{
vector<vector<int>> DP(A.size() + 1, vector<int>(B.size() + 1));
for (int i = 0; i <= A.size(); i++)
{
for (int j = 0; j <= B.size(); j++)
{
if (i == 0 || j == 0)
{
DP[i][j] = 0;
}
else 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]);
}
}
}
string lcs = ReconstructLCS(DP, A, B, A.size(), B.size());
return lcs;
}Ref) 코딩테스트를 위한 자료구조 + 알고리즘 with C++
'Algorithm > DP' 카테고리의 다른 글
| [Algorithm/DP] 부분집합의 합 문제(브루트포스, 백트래킹, 메모이제이션, 타뷸레이션) (0) | 2024.08.02 |
|---|---|
| [Algorithm/DP] 동적 계획법(Dynamic Programming) (0) | 2024.08.01 |