Suhwanc

문제 링크 :https://www.acmicpc.net/problem/9252

 

9252번: LCS 2

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

 

풀이

가장 간단한 LCS(Longest Common Subsequence)를 찾는 문제입니다.

LCS 문자열 찾기 : https://suhwanc.tistory.com/80

 

LCS 알고리즘

1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence)이란 어떤 단어에서 연속되지 않는 부분 문자열을 뜻하는데..

suhwanc.tistory.com

소스 코드

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
#include <iostream>
#include <algorithm>
using namespace std;
int d[1001][1001];
int main()
{
    string temp1, temp2;
    cin >> temp1 >> temp2;
 
    string a, b;
    a = " " + temp1;
    b = " " + temp2;
 
    int na = a.size();
    int nb = b.size();
 
    for (int i = 1; i < na; i++) { // LCS 문자 길이 찾기
        for (int j = 1; j < nb; j++) {
            if (a[i] == b[j]) {
                d[i][j] = d[i - 1][j - 1+ 1;
            }
            else {
                d[i][j] = max(d[i][j - 1], d[i - 1][j]);
            }
        }
    }
    printf("%d\n", d[na-1][nb-1]);
    string ans;
    int i = na - 1;
    int j = nb - 1;
 
    while (d[i][j] != 0) {
        if (d[i][j] == d[i][j - 1]) { //앞의 값과 같다면
            j--;
        }
        else if (d[i][j] == d[i-1][j]) { //위의 값과 같다면 
            i--;
        }
        else { //대각선이 1차이
            ans += a[i];
            i--;
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
    return 0;
}
 
cs

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~

'백준 문제풀이' 카테고리의 다른 글

백준 1946번 신입사원  (0) 2020.08.05
백준 5052번 전화번호 목록  (0) 2020.05.06
백준 9252번 LCS 2  (0) 2020.02.12
백준 5582번 공통 부분 문자열  (0) 2020.02.12
백준 9251번 LCS  (0) 2020.02.12
백준 10422번 괄호  (2) 2020.02.12