반응형

https://www.acmicpc.net/problem/5582

 

5582번: 공통 부분 문자열

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열 str1, str2를 입력 받습니다.

 

2. str1[ i ] 와 str2[ j ]가 일치할 때 arr[ i ][ j ] = arr[ i - 1 ][ j - 1 ]  + 1의 점화식을 통해 최댓값을 ans에 저장합니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<string>
 
using namespace std;
 
int arr[4001][4001];
int ans;
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    string str[2];
 
    cin >> str[0] >> str[1];
 
    str[0] = '1' + str[0];
    str[1] = '1' + str[1];
 
    for (int i = 1; i < str[0].size(); i++) {
        for (int j = 1; j < str[1].size(); j++) {
            if (str[0][i] == str[1][j]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
                ans = max(ans, arr[i][j]);
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2228번 - 구간 나누기 (C++)  (0) 2022.10.24
[ 백준 ] 2133번 - 타일 채우기 (C++)  (0) 2022.10.23
[ 백준 ] 2225번 - 합분해 (C++)  (0) 2022.10.21
[ 백준 ] 2011번 - 암호코드 (C++)  (0) 2022.10.20
[ 백준 ] 2631번 - 줄세우기 (C++)  (0) 2022.10.19
반응형

https://www.acmicpc.net/problem/9251

 

9251번: LCS

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

LCS란 Longest Common Subsequence 즉, 최장 공통부분 수열을 찾는 것입니다. 이 문제는 모든 수열의 부분수열 중에서 공통이 되는 가장 긴 수열의 길이를 구하는 문제입니다.

 

가장 긴 수열을 찾기 위해서는 각 수열의 요소들을 하나씩 비교해서 만약 같다면 바로 전의 최장 수열 길이의 최댓값에 +1을 해주고 같지 않다면 이전의 최장 수열 길이 중 최댓값을 대입해주면 됩니다.

 

이해하기 쉽게 다음 두 수열을 예로 들어서 설명하겠습니다.

ACAYKP
CAPCAK

먼저 문자열의 최대 길이는 1000이므로 dp[ 1001 ][ 1001 ]의 배열을 만들어줍니다. 그리고 각각의 값들을 비교하면서 위에서 설명한 대로 값들을 대입합니다. 쉬운 비교를 위해서 모든 수열의 0번째 요소를 1번으로 설정합니다.

 

 

다음으로 각 요소들을 비교해가면서 서로 같은 문자라면 dp [ i - 1 ][ j - 1 ] + 1의 값을 대입해줍니다.

 

그렇지 않다면 바로 직전까지의 수열의 최댓값 즉, dp[dp [ i - 1 ][ j ]와 dp [ i ][ j - 1 ] 중 더 큰 값을 대입해줍니다.

 

먼저 str[ 0 ][ 1 ]인 'A'와 str [ 1 ][ 1 ]인 'C'는 서로 다르기 때문에 dp [ 0 ][ 1 ]과 dp [ 1 ][ 0 ]중 더 큰 값을 dp [ 1 ][ 1 ]에 대입해줍니다.

 

다음으로 str[ 0 ][ 1 ]인 'A'와 str [ 1 ][ 2 ]인 'A'는 서로 같으므로 dp [ 0 ][ 1 ] + 1을 dp [ 1 ][ 2 ]에 대입해줍니다. 이런 식으로 쭉 대입을 해주다 보면 다음과 같은 표가 완성됩니다.

 

 

그리고 마지막에 dp[ 6 ][ 6 ]을 출력해주면 가장 긴 부분 수열의 길이를 구할 수 있습니다.

 

[ 소스 코드 ]

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
#include <iostream>
#include <string>
 
using namespace std;
 
int dp[1001][1001];
 
int main()
{
    string str[2];
 
    for (int i = 0; i < 2; i++) {
        cin >> str[i];
        str[i] = '0' + str[i];        //수열을 1부터 시작하기 위해서 맨 앞에 더미 문자를 넣음
    }
 
    for (int i = 1; i < str[0].size(); i++) {
        for (int j = 1; j < str[1].size(); j++) {    //각 문자들을 비교하며 최장 부분수열의 길이를 경신
            if (str[0][i] == str[1][j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
 
    cout << dp[str[0].size() - 1][str[1].size()-1];
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 11779번 - 최소비용 구하기 2 (C++)  (0) 2022.06.04
[ 백준 ] 17070번 - 파이프 옮기기 1 (C++)  (0) 2022.06.03
[ 백준 ] 15686번 - 치킨 배달 (C++)  (0) 2022.06.01
[ 백준 ] 1149번 - RGB거리 (C++)  (0) 2022.05.31
[ 백준 ] 1799번 - 비숍 (C++)  (0) 2022.05.30

+ Recent posts

티스토리툴바