-
들어가기에 앞서
부분 문자열?
①Substring ? 연속된 부분 문자열
②Subsequence ? 연속되지 않은 부분 문자열
예시로 ACDEF와 ABKEF가 있다고 하자.
substring = EF
ACDEF
ABKEF
subsequece = AEF
ACDEF
ABKEF
LCS (Longest Common Subsequence, 최장 공통 부분 문자열)
- 개념 : 두개의 문자열을 비교해 공통 부분 수열을 구하는 알고리즘
- 사용처 : 염기 서열 유사성 분석 or 음파 담어 검색 등
- 구현 방법 : DP(동적분석법)으로 특정 범위까지 memoization하고, 다음 범위를 구할때 이전에 저장한 값을 이용해 품.
예시로 ACAYKP, CAPCAK 문자열의 LCS를 구해보자.참고* 테이블의 첫번째 열과 첫번째 행은 0으로 채워둔다 (계산의 용이성을 위해)* 하나의 문자열을 기준 문자열로 잡고, 다른 문자열을 비교 문자열로 둔다.지금은 ACAYKP를 기준 문자열, CAPCAK 비교 문자열로 사용해 보겠다.일단 첫번째로 CAPCAK 단어 중 첫번째 단어인 C만 이용해서 ACAYKP와 비교해보겠다.((테이블 안에 들은 수는 공통 부분 문자열의 개수이다.))
그다음 CAPCAK 중 CA를 비교해보겠다.
이런식으로 테이블을 작성하다 보면 규칙을 발견할 수 있다.
(행은 이전 행의 값을 기반으로 계산된다는 점.)
현재 테이블에 들어갈 수는
비교문자가 같을 때 -> 이전까지의 LCS 길이 + 1
즉, 왼쪽 대각선 값 + 1
비교문자가 다를 때 -> 이전까지의 LCS 길이
즉, 왼쪽과 위쪽 중 큰 값
규칙을 통해 만들어진 최종적인 테이블을 아래와 같다.
결과적으로 LCS의 길이를 구할 수 있다. = 4
그렇다면 길이가 아닌 LCS의 해당하는 부분 수열을 구하는 방법은?
가장 오른쪽 아래부터 시작한다.
1. 자신과 같은 숫자가 있는 곳으로 이동한다.
2. 왼쪽과 위쪽에 같은 수가 없다면, 대각선 방향이 현재 값 -1인지 보고 그 수로 이동한다.
(비교 문자가 같을때 왼쪽 대각선에서 +1 했으니, 이제는 반대로 가는 것이다.)
이를 계속 반복하다 0을 만나면 그만한다.
ACAYKP, CAPCAK 문자열의 LCS는 ACAK 이다.
실제 LCS 구현 코드는 아래에 있다
[백준] 9252 LCS2 문제의 정답
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <stdio.h>#include <string>#include <algorithm>#include <iostream>#include <vector>using namespace std;string f, s;int dp[1001][1001];int main() {cin >> f >> s;// 첫번째행과 첫번째열이 0이여야하니깐 계산상 편의를 위해 문자열 앞에 의미없는 걸 붙여둔다.f.insert(f.begin(), '0');s.insert(s.begin(), '0');//1. 테이블 채우기for (int i = 1; i < f.length(); i++) {for (int j = 1; j < s.length(); j++) {if (f[i] == s[j]) { // 문자가 같다면, 왼쪽 대각선 값 + 1dp[i][j] = dp[i - 1][j - 1] + 1;}else {//문자가 다르면, 왼쪽과 위쪽 값 중 큰 값dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);}}}printf("%d\n", dp[f.length()-1][s.length()-1]);vector <char> temp;//2. 문자열 구하기int i = f.length() - 1;int j = s.length() - 1;while (dp[i][j] != 0) {//같은 숫자있다면 이동if (dp[i][j] == dp[i][j - 1]) {j -= 1;}else if (dp[i][j] == dp[i - 1][j]) {i -= 1;}else if (dp[i][j] == dp[i - 1][j - 1] + 1) {temp.insert(temp.begin(),f[i]); //거꾸로 삽입되지 않기 위해, 처음에 계속 삽입i -= 1;j -= 1;}}for (int i = 0; i < temp.size(); i++) {printf("%c", temp[i]);}return 0;}cs '알고리즘' 카테고리의 다른 글
에라토스테네스의 체 (0) 2020.07.16 MST (0) 2020.05.16 brute force (0) 2020.03.26 Lazy propagation (0) 2020.03.17 Segment Tree (0) 2020.03.17