1. 문제
1) 문제 링크
: www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
2) 설명
2. 풀이
1) 알고리즘
: DP
2) 풀이 설명
두 문자열이 주어질 때 가장 긴 공통 문자열의 길이와 그 문자열을 추출하는 문제.
ex) ABCDEG, BDAEFG 라면 BDEG가 가장 긴 공통 문자열이 되고 길이는 4가 된다.
첫 접근은 DP를 사용해서 공통 문자열의 길이를 구했다.
예를 들어 문자열 A, B가 주어지면 solve(A_idx, B_idx)를 재귀적으로 사용해서 가장 긴 문자열의 길이를 구하는 방식이다.
dp[x][y] 에는 A의 x번째 문자, B의 y번째 문자로부터 만들 수 있는 가장 긴 공통 문자열의 길이를 반환한다.
그러나 이 방식으로는 문자열의 길이는 구해도 어떤 문자열인지 추적하는 일이 너무 힘들었다.
그래서 검색 결과 다른 방식으로 DP를 사용하는 법을 배웠다.
일단 탑다운 방식보다는 바텀업 방식으로 진행해나갔다.
dp[i][j] 는 A의 i번째 문자까지와 B의 j-1번째 문자까지, B의 j번째 문자까지와 A의 i-1번째 문자까지 비교했을 때 가장 긴 공통 문자열의 길이를 의미한다.
그러므로 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])이 된다.
이부분이 상당히 이해하기 까다로웠다.
내가 이해한 바로는 (A[i], B[j-1])로 만들 수 있는 가장 긴 공통 문자열의 길이, (A[i-1], B[j])로 만들 수 있는 가장 긴 공통 문자열의 길이는 (A[i-1], B[j-1])로 만들 수 있는 가장 긴 공통 문자열의 길이와 같거나 1개 더 크기 때문으로 이해했다.
이렇게 다 돌고나면 dp[A의 길이][B의 길이]가 가장 긴 공통 문자열의 길이가 된다.
이후 만들어놓은 자취를 따라서 역추적해서 정답 문자열을 추출해내면 된다.
3. 코드
/*
LCS 2
DP
Top-down
길이만 구할 수 있었다..
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000
using namespace std;
string A = "", B = "";
vector<vector<int>> dp(MAX, vector<int>(MAX, -1));
int solve(int A_idx, int B_idx){
if(A_idx == A.length() || B_idx == B.length())
return 0;
if(dp[A_idx][B_idx]>=0)
return dp[A_idx][B_idx];
for(int i=A_idx;i<A.length();i++){
for(int j=B_idx;j<B.length();j++){
if(A[i] == B[j]){
dp[A_idx][B_idx] = max(dp[A_idx][B_idx], solve(i+1, j+1)+1);
}
}
}
return dp[A_idx][B_idx];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> A >> B;
cout << solve(0, 0) << "\n";
return 0;
}
/*
LCS 2
DP
Bottom-up
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string A = "", B = "";
cin >> A >> B;
vector<vector<int>> dp(MAX, vector<int>(MAX, 0));
//길이 구하기
for(int i=1;i<=A.length();i++){
for(int j=1;j<=B.length();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]);
}
}
}
cout << dp[A.length()][B.length()] << endl;
//경로 찾아가기
string answer = "";
int x = A.length();
int y = B.length();
while(dp[x][y]>0){
if(dp[x][y] == dp[x-1][y]){
x--;
} else if(dp[x][y] == dp[x][y-1]){
y--;
} else {
answer = A[x-1] + answer;
x--;
y--;
}
}
cout << answer << endl;
return 0;
}
4. 느낀점
- 머리로는 대강 알겠는데 설명하는 게 너무 어렵다. 대강 이해한 게 문제인 것 같다.. 내 생각을 남들이 이해할 수 있도록 표현하는 연습을 하는 것도 중요하니까 어렵더라도 계속 설명하려 노력해야겠다.
- 단순히 길이만을 구하는 탑다운 풀이에서 벗어나오지를 못했다... 안 될 것 같으면 고집부리지 말고 다른 방식의 풀이도 생각해보자.
'알고리즘 > 백준' 카테고리의 다른 글
| [백준/9656] 돌 게임 2 (0) | 2020.11.02 |
|---|---|
| [백준/2631] 줄세우기 (0) | 2020.11.02 |
| [백준/11501] 주식 (0) | 2020.10.18 |
| [백준/15312] 이름 궁합 (1) | 2020.10.18 |
| [백준/17070] 파이프 옮기기 1 (0) | 2020.10.18 |