이전 글
2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (A), 백준 9251 LCS
LCS(Longest Common Subsequence) 알고리즘 (A), 백준 9251 LCS
LCS 알고리즘을 공부해보자. 이 글은 백준 문제집 "LCS"을 바탕으로 합니다! https://www.acmicpc.net/workbook/view/5080 문제집: LCS (baekjoon) www.acmicpc.net 첫번째 문제, https://www.acmicpc.net/problem..
rhtkdwls.tistory.com
에 이어서, 백준 9252 LCS2 문제를 풀어보겠습니다.
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
이번에 문제에서 요구하는 것은 "백준 9251 - LCS"에 더해집니다.
실제 "LCS"를 출력하는 것입니다! 와우!
이전 "백준 9251 - LCS" 글에서 사용했던 "ACAYKP", "CAPCAK" 테이블을 활용해봅시다.
| (0) | C(1) | A(2) | P(3) | C(4) | A(5) | K(6) | |
| (0) | 0 | 0(left) | 0(left) | 0(left) | 0(left) | 0(left) | 0(left) |
| A(1) | 0(up) | 0(up) | 1(wow!) | 1(left) | 1(left) | 1(wow!) | 1(left) |
| C(2) | 0(up) | 1(wow!) | 1(up) | 1(up) | 2(wow!) | 2(left) | 2(left) |
| A(3) | 0(up) | 1(up) | 2(wow!) | 2(left) | 2(up) | 3(wow!) | 3(left) |
| Y(4) | 0(up) | 1(up) | 2(up) | 2(up) | 2(up) | 3(up) | 3(left) |
| K(5) | 0(up) | 1(up) | 2(up) | 2(up) | 2(up) | 3(up) | 4(wow!) |
| P(6) | 0(up) | 1(up) | 2(up) | 3(wow!) | 3(left) | 3(left) | 4(up) |
우리가,
경우 1) A[i] = B[j]
경우 2) A[i] != B[j]
일 때를 각각 나누어 보았기 때문에, 테이블의 값 옆에 "방향"을 작성해봤습니다.
- "경우 1"인 것은 (wow!)라고 썼습니다.
- "경우 2"인 것은 max(DP[i - 1][j], DP[i][j - 1]) 중에서 선택된 방향(left, up)을 썼습니다.(두 값이 똑같다면 암거나 썼습니다.)
이 문제에서 우리가 원하는 것은 뭐였죠? 실제 "LCS"도 출력하는 것이었죠.
이 "LCS"를 출력하는 것은 위의 테이블에서 각각의 값들을 계산했을 당시로 돌아가보면 됩니다.
위의 테이블의 6행, 6열에서 출발해서 그때 당시의 상황을 떠올려 봅시다.
- 6행 6열 : 위(up)로 갔던 것 같아.
- 5행 6열 : 대각선(wow)으로 갔던 것 같아.
- 4행 5열 : 위(up)로 갔던 것 같아.
- 3행 5열 : 대각선(wow)으로 갔던 것 같아.
- 2행 4열 : 대각선(wow)으로 갔던 것 같아.
- 1행 3열 : 옆(left)으로 갔던 것 같아.
- 1행 2열 : 대각선(wow)으로 갔던 것 같아.
- 0행 1열 : 옆(left)으로 갔던 것 같아.
- 0행 0열 : 도착~!
이렇게 출력하면 됩니다.
그러면, 언제 해당 문자를 출력하냐고요? 대각선(wow)을 가리킬 때만 출력하면 됩니다!공통 문자열이라는 것이 두 문자열 모두 같은 문자를 가지는 것이기 때문에, 대각선으로 이동할 때만 출력하면 됩니다!!!
그렇다면, 방향이 어떤지는 어떻게 아나고요?
- "문자열 A의 i번째 문자와, 문자열 B의 j번째 문자가 같았을 때", 우리는 대각선에 있는 값을 참조했었습니다.
- "문자열 A의 i번째 문자와, 문자열 B의 j번째 문자가 같지 않을 때", 우리는 위(up)와 옆(left)의 값 중 큰 값을 선택했습니다. (둘이 같다면 암거나)
이런 방법이 귀찮으시다면, "방향"을 저장할 새로운 2차원 배열을 만들어 주어도 됩니다.
끝)
코드 - JAVA
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
import java.io.*;
public class Main {
private static BufferedWriter bw;
private static String A, B;
private static int[][] dp_length;
private static char[][] dp_direction;
private static void print(int i, int j) throws IOException {
if (i < 0 || j < 0) return;
if (dp_direction[i][j] == 'i') {
print(i - 1, j);
}
if (dp_direction[i][j] == 'j') {
print(i, j - 1);
}
if (dp_direction[i][j] == 'k') {
print(i - 1, j - 1);
bw.append(A.charAt(i));
}
}
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
A = br.readLine();
B = br.readLine();
dp_length = new int[A.length()][B.length()];
dp_direction = new char[A.length()][B.length()];
//fill column 0 of int[][] dp.
if (A.charAt(0) == B.charAt(0)) {
dp_length[0][0] = 1;
dp_direction[0][0] = 'k';
}
for (int j = 1; j < B.length(); j++) {
if (dp_length[0][j - 1] == 1) {
dp_length[0][j] = 1;
dp_direction[0][j] = 'j';
} else if (A.charAt(0) == B.charAt(j)) {
dp_length[0][j] = 1;
dp_direction[0][j] = 'k';
}
}
//fill column 1 ~ of int[][] dp.
for (int i = 1; i < A.length(); i++) {
if (dp_length[i - 1][0] == 1) {
dp_length[i][0] = 1;
dp_direction[i][0] = 'i';
} else if (A.charAt(i) == B.charAt(0)) {
dp_length[i][0] = 1;
dp_direction[i][0] = 'k';
}
for (int j = 1; j < B.length(); j++) {
if (A.charAt(i) == B.charAt(j)) {
dp_length[i][j] = dp_length[i - 1][j - 1] + 1;
dp_direction[i][j] = 'k';
} else if (dp_length[i - 1][j] > dp_length[i][j - 1]){
dp_length[i][j] = dp_length[i - 1][j];
dp_direction[i][j] = 'i';
} else {
dp_length[i][j] = dp_length[i][j - 1];
dp_direction[i][j] = 'j';
}
}
}
int length = dp_length[A.length() - 1][B.length() - 1];
if (length == 0) {
bw.append("0");
} else {
bw.append(String.valueOf(length) + "\n");
print(A.length() - 1, B.length() - 1);
}
br.close();
bw.flush();
bw.close();
}
}
|
cs |
다음글
2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (C), 백준 1958 LCS3(JAVA)
LCS(Longest Common Subsequence) 알고리즘 (C), 백준 1958 LCS3(JAVA)
이전 글 2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (B), 백준 9252 LCS2 LCS(Longest Common Subsequence) 알고리즘 (B), 백준 9252 LCS2 이전 글 2020/07/10 - [공부] - LCS(Longest Comm..
rhtkdwls.tistory.com
'공부' 카테고리의 다른 글
| LCS(Longest Common Subsequence) 알고리즘 (F), 백준 18439 LCS6(C++) (3) | 2020.09.15 |
|---|---|
| LCS(Longest Common Subsequence) 알고리즘 (E), 백준 18438 LCS5(C++) (1) | 2020.07.10 |
| LCS(Longest Common Subsequence) 알고리즘 (D), 백준 13711 LCS4(JAVA) (0) | 2020.07.10 |
| LCS(Longest Common Subsequence) 알고리즘 (C), 백준 1958 LCS3(JAVA) (0) | 2020.07.10 |
| LCS(Longest Common Subsequence) 알고리즘 (A), 백준 9251 LCS(JAVA) (0) | 2020.07.10 |
