[백준] 9252. LCS 2 (Longest Common Subsequence)
2020. 3. 26. 17:57
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
최장 부분 문자열 문제였습니다.
Substring과 달리 Subsequence는 연속적이지 않아도 됩니다.
이번 문제는 LCS문자열의 길이뿐 아니라 문자열까지 출력하는 문제입니다.
LCS의 길이를 구할때마다 String[][] 배열에 해당 좌표가 왼쪽 대각선 + 1 인지, 왼쪽 길이 인지, 위 쪽 길이 인지 체크해줍니다.
길이를 구한 후, 문자열을 찾아줍니다.
"diagonal"(대각선)으로 저장되어 있는 좌표면 해당 좌표의 문자를 정답 문자열에 추가해줍니다.
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 1068. 트리 (0) | 2020.03.30 |
|---|---|
| [백준] 1991. 트리 순회 (0) | 2020.03.27 |
| [백준] 5582. 공통 부분 문자열 (LCS, Longest Common Substring) (0) | 2020.03.26 |
| [백준] 1922. 네트워크 연결(MST, Kruskal) (0) | 2020.03.25 |
| [백준] 9251 LCS (0) | 2020.03.11 |