9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
0. 기본 LCS 알고리즘 : 문자열 A와 B의 끝 문자가 x로 같다면, LCS의 길이는 A'와 B'의 LCS + 1 이다
- 여기서 A', B'이란 맨 끝문자를 제외한 A, B
- A = A'+x, B = B'+x
- A와 B의 끝 문자가 x,y로 다르다면, LCS의 길이는 A'와 B의 LCS, A와 B'의 LCS 둘 중 큰 쪽이다
- A = A'+x, B = B'+y
1. 위 과정을 DP로 계산하면서 모든 계산 결과를 저장한다
2. LCS문자열 찾기 : DP를 역으로 추적한다
- DP[x][y]의 값이 DP[x][y-1]와 같다면 : 해당 칸으로부터 온 값, y--
- DP[x][y]의 값이 DP[x-1][y]와 같다면 : 해당 칸으로부터 온 값, x--
- 둘 다 아니라면 : LCS로서 진행된 칸, x--, y--, 해당 위치의 문자를 저장
3. 역순으로 찾았으므로, 뒤집어서 출력해준다
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String fst = br.readLine();
String snd = br.readLine();
int len = fst.length();
int sndLen = snd.length();
int[][]dp = new int[len+1][sndLen+1];
for (int i = 0; i < len; i++) {
char f = fst.charAt(i);
for (int j = 0; j < sndLen; j++) {
char s= snd.charAt(j);
if(s==f) {
dp[i+1][j+1] = 1 + dp[i][j];
}
else {
dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
}
}
}
int x = len, y=sndLen;
while(sb.length()!=dp[len][sndLen]) {
if(dp[x][y]==dp[x][y-1]) {
y--;
}else if(dp[x][y]==dp[x-1][y]) {
x--;
}else {
x--;y--;
sb.append(fst.charAt(x));
}
}
System.out.println(dp[len][sndLen]);
System.out.println(sb.reverse());
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글
| [백준] 4195 - 친구 네트워크 (0) | 2021.04.28 |
|---|---|
| [백준] 1976 - 여행 가자 (0) | 2021.04.28 |
| [백준] 1717 - 집합의 표현 (0) | 2021.04.28 |
| [백준] 1644 - 소수의 연속합 (0) | 2021.04.22 |
| [백준] 1937 - 욕심쟁이 판다 (0) | 2021.04.22 |
| [백준] 1865 - 웜홀 (0) | 2021.04.22 |
| [백준] 1261 - 알고스팟 (0) | 2021.04.21 |
