먼저 용어를 간단히 정리하자면, LCS(Longest Common Subsequence) 로 Subsequence 는 부분 수열이기 때문에, 꼭 연속적인 문자열일 필요가 없다. 만약 substring 이면 연속적인 문자열이다.

 

 

O(N^2)

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

 

9251번: LCS

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

www.acmicpc.net

 

DP 정의는 다음과 같다.

dp[p][q] : 첫 번째 문자열 p, 두 번째 문자열 q 위치까지의 LCS 길이

  if string_1 [p] == string_2 [q]:
       dp[p][q] = dp[p-1][q-1] + 1
  else :
       dp[p][q] = max( dp[p-1][q], dp[p][q-1] )

 위 dp 정의에 따라 두 문자열의 dp 배열 저장 값(그림)을 보면 이해하기 쉽다.

 

# Top-down

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
int dp[1001][1001];
string s1, s2;
 
int inline max(int a,int b){return a>b?a:b;}
int solve(int p, int q){
    if(p < 0 || q < 0) 
        return 0;
    
    int &ret = dp[p][q];
    if(ret != -1){
        return ret;
    }
 
    int h = 0;
    if(p >= 0){
        h = max(h, solve(p-1, q));
    }
 
    if(s1[p] == s2[q]){
        h = max(h, solve(p-1, q-1)+1);
    }
 
    if(q >= 0){
        h = max(h, solve(p, q-1));
    }
 
    return ret = h;
}
 cs

 

# Bottom-up

1
2
3
4
5
6
7
8
9
10
11
int dp[1001][1001];
string s1, s2;
 
for(int i=0; i < s1.length(); i++){
    for(int j=0; j < s2.length(); j++){
        dp[i][j] = max( (i==0 ? 0 : dp[i-1][j]), (j==0 ? 0 : dp[i][j-1]));
        if(s1[i] == s2[j]){
            dp[i][j] = max(dp[i][j], (i == 0 || j == 0 ? 0 : dp[i-1][j-1]) + 1);
        }
    }
}
 cs

 

 

# 9251 LCS 소스 코드

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
#include<iostream>
#include<string>
#include<cstring>
 
using namespace std;
int dp[1001][1001];
string s1, s2;
 
int inline max(int a,int b){return a>b?a:b;}
int solve(int p, int q){
    if(p < 0 || q < 0) 
        return 0;
    
    int &ret = dp[p][q];
    if(ret != -1){
        return ret;
    }
 
    int h = 0;
    if(p >= 0){
        h = max(h, solve(p-1, q));
    }
 
    if(s1[p] == s2[q]){
        h = max(h, solve(p-1, q-1)+1);
    }
 
    if(q >= 0){
        h = max(h, solve(p, q-1));
    }
 
    return ret = h;
}
int main(){
    memset(dp, -1, sizeof(dp));
    cin>>s1>>s2;
 
    // cout<< solve(s1.length()-1, s2.length()-1) <<endl;
    // printf("\t");
    // for(int i=0;i<s2.length(); i++){
    //     printf(" %c", s2[i]);
    // }
    // printf("\n");
    for(int i=0; i < s1.length(); i++){
        // printf("%5c\t:", s1[i]);
        for(int j=0; j < s2.length(); j++){
            dp[i][j] = max( (i==0 ? 0 : dp[i-1][j]), (j==0 ? 0 : dp[i][j-1]));
            if(s1[i] == s2[j]){
                dp[i][j] = max(dp[i][j], (i == 0 || j == 0 ? 0 : dp[i-1][j-1]) + 1);
            }
            // printf("%d ", dp[i][j]);
        }
        // printf("\n");
    }
    cout<<dp[s1.length()-1][s2.length()-1] <<endl;
    return 0;
}
 cs

 

O(N^2), LCS 문자열 출력

LCS 문자열까지 출력하기 위해선 dp 의 마지막 인덱스(dp[s1.length()-1][s2.length()-1]) 부터 0,0 까지 이동해가며, 문자열을 추적해야한다.

 

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

 

9252번: LCS 2

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

www.acmicpc.net

 

9252 LCS 2 소스코드

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
#include<iostream>
#include<string>
#include<cstring>
 
using namespace std;
int dp[1001][1001];
string s1, s2;
 
int inline max(int a,int b){return a>b?a:b;}
int solve(int p, int q){
    if(p < 0 || q < 0) 
        return 0;
    
    int &ret = dp[p][q];
    if(ret != -1){
        return ret;
    }
 
    int h = 0;
    if(p >= 0){
        h = max(h, solve(p-1, q));
    }
 
    if(s1[p] == s2[q]){
        h = max(h, solve(p-1, q-1)+1);
    }
 
    if(q >= 0){
        h = max(h, solve(p, q-1));
    }
 
    return ret = h;
}
int main(){
    memset(dp, -1, sizeof(dp));
    cin>>s1>>s2;
 
    // cout<< solve(s1.length()-1, s2.length()-1) <<endl;
    // printf("\t");
    // for(int i=0;i<s2.length(); i++){
    //     printf(" %c", s2[i]);
    // }
    // printf("\n");
    for(int i=0; i < s1.length(); i++){
        // printf("%5c\t:", s1[i]);
        for(int j=0; j < s2.length(); j++){
            dp[i][j] = max( (i==0 ? 0 : dp[i-1][j]), (j==0 ? 0 : dp[i][j-1]));
            if(s1[i] == s2[j]){
                dp[i][j] = max(dp[i][j], (i == 0 || j == 0 ? 0 : dp[i-1][j-1]) + 1);
            }
            // printf("%d ", dp[i][j]);
        }
        // printf("\n");
    }
    cout<<dp[s1.length()-1][s2.length()-1] <<endl;
    int p = s1.length()-1, q = s2.length()-1;
    string ans = "";
    while(p >= 0 && q >= 0){
        if(s1[p] == s2[q]){
            ans = s1[p] + ans;
            p--; q--;
            continue;
        }
        if(p > 0 && dp[p-1][q] == dp[p][q]){
            p--;
        }
        else if(q > 0 && dp[p][q-1] == dp[p][q]){
            q--;
        } else {
            break;
        }
    }
    cout << ans << endl;
    return 0;
}
 cs

 

 

 

BOJ 1958 LCS 3

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

 

1958번: LCS 3

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다)

www.acmicpc.net

이 문제는 문자열 3개의 LCS 문제이며, dp를 2차원에서 3차원으로 확장하여 풀면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<string>
using namespace std;
string s1,s2,s3;
int dp[101][101][101];
int main(){
    cin >> s1 >> s2 >> s3;
    int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
    for(int i = 1 ; i <= s1len; i++){
        for(int j = 1 ; j <= s2len; j++){
            for(int p = 1 ; p <= s3len; p ++){
                dp[i][j][p] = max(dp[i-1][j][p], max(dp[i][j-1][p], dp[i][j][p-1]));
                if(s1[i-1] == s2[j-1] && s2[j-1] == s3[p-1]){
                    dp[i][j][p] = max(dp[i][j][p], dp[i-1][j-1][p-1] + 1);
                }
            }
        }
    }
    cout<< dp[s1len][s2len][s3len] << endl;
    return 0;
}
 
 cs

 

 

O(n log n) 방법

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

 

13711번: LCS 4

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] �

www.acmicpc.net

이 문제는 n 의 길이가 100,000 까지 이므로, 기존의 O(n^2) 방법으로는 풀 수 없다. O(n log n)으로 풀기 위해선 조건이 필요한데, 문제에 쓰여있듯이 하나의 문자는 한 번만 나타나야 한다. 한 번씩 나타날 때, 이 문제를 LIS 로 응용해서 풀 수 있는데, 방법은 다음과 같다.

 

 1. 수열 A 의 값 A[i] 을 인덱스 배열 C에 저장한다. C[ A[i] ] = i
 2. 수열 B의 값을 A 값에 따른 인덱스 배열로 치환한다. B[i] = C[ B[i] ]
 3. B 배열에 LIS 를 구한다.

 

즉, A 값의 인덱스로 B 배열 값을 치환한 뒤, LIS 를 구하면 두 문자열의 LCS가 된다. 

 

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
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
 
int n, idx[100001], A[100001], B[100001];
 
int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d", &A[i]);
        idx[A[i]] = i;
    }
    vector<int> ans;
    for(int i=0;i<n;i++){
        scanf("%d", &B[i]);
        B[i] = idx[B[i]];
        if( ans.empty() || ans.back() < B[i])
            ans.push_back(B[i]);
        else {
            vector<int>::iterator it = lower_bound(ans.begin(), ans.end(), B[i]);
            *it = B[i];
        }
    }
    printf("%d\n", ans.size());
    return 0;
}
 cs

 

저작자표시

'알고리즘 문제풀이' 카테고리의 다른 글

1516 게임 개발  (0) 2020.09.04
BOJ 2407 조합  (0) 2020.09.04
BOJ 가장 긴 증가하는 부분 수열  (0) 2020.09.02
BOJ 4811 알약  (0) 2020.08.28
BOJ 12865 평범한 배낭  (0) 2020.08.28

이 문제 시리즈는 출력 값이 길이만 출력하는지, 긴 수열 또한 출력해야 하는지에 따라 풀이 방법이 달라지고, n 조건에 따라 풀이 방법이 달라진다.

 

1 단계 O(n^2), 가장 긴 수열의 길이만 출력

 

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

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

이 문제는 입력 조건 n 의 크기에 따라 풀이 방법이 달라지고, 먼저 11053 번 문제는 n 조건이 1000 까지 이므로 n^2 만에 풀이 가능하며, 이전 배열값을 다시 참조하면서, 가장 긴 값을 저장하면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<algorithm>
using namespace std;
int n, arr[1001],cnt[1001],ans=1;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    for (int i = 0; i < n; i++) {
        cnt[i] = 1;
        for (int j = i - 1; j >= 0; j--) {
            if (arr[i] > arr[j]) {
                cnt[i] = max(cnt[i],cnt[j]+1);
                ans = max(ans, cnt[i]);    
            }
        }
    }
    printf("%d", ans);
    return 0;
}
 cs

 

 

2 단계 O( n log n), 가장 긴 수열의 길이만 출력

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

 

12015번: 가장 긴 증가하는 부분 수열 2

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

www.acmicpc.net

 두 번째 문제는 1 단계 문제와 같이 길이만 출력하지만, n의 조건이 크기 때문에 O(N^2)만에 해결할 수 없다. 따라서 이 문제는 1번 문제 풀이에서 가장 긴 수열의 길이를 탐색해가는 과정을 log n으로 줄여야 풀 수 있다. 

 풀이 방법은 하나의 벡터를 정의하여, 가장 마지막 값이 현재 탐색하는 값보다 클 경우 이진 탐색을 통해 현재 탐색 값이 들어갈 위치를 찾아 수정한다. 주의할 점은 이렇게 풀었을 때, 정의한 벡터 안의 값이 가장 긴 부분 수열이라고 보장하지 않는다.

 

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
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, arr[1000001];
 
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d", &arr[i]);
    }
 
    vector<int> ans;
    ans.push_back(arr[0]);
    for(int i=1;i<n;i++){
        if(ans.back() < arr[i]){
            ans.push_back( arr[i] );
        } else {
            vector<int>::iterator it = lower_bound(ans.begin(), ans.end(), arr[i]);
            *it = arr[i];
        }
    }
    printf("%d", ans.size());
    return 0;
}
 cs

 

 

 

3단계, O(N^2) 수열까지 출력

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

 

14002번: 가장 긴 증가하는 부분 수열 4

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

이 문제는 가장 긴 수열의 길이와 더불어 긴 수열까지 모두 출력해야 한다. 위에서 말했듯이 2단계 풀이로는 가장 긴 수열이라고 보장하지 않기 때문에 풀 수 없다. 다행히 이 문제는 다시 n 조건이 작아 졌기 때문에, 각 배열 값을 참조하면서 현재까지 가장 긴 수열들을 모두 저장할 수 있다.

 

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
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, arr[1001], len[1001];
 
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d", &arr[i]);
    }
 
    vector<int> ans[1001];
    int ans_idx = 0, ans_len = 1;
    for(int i=0;i<n;i++){
        len[i] = 1;
        for(int j=i-1; j >= 0; j--){
            if(arr[i] > arr[j] && len[i] < len[j] + 1){
                len[i] = len[j] + 1;
                ans[i].clear();
                ans[i].insert(ans[i].end(), ans[j].begin(), ans[j].end());
                if(ans_len < len[i]){
                    ans_len = len[i];
                    ans_idx = i;
                }
            }
        }
        ans[i].push_back(arr[i]);
    }
    printf("%d\n", ans_len);
    for(int i=0;i<ans_len;i++){
        printf("%d ",ans[ans_idx][i]);
    }
    return 0;
}
 cs

 

 

 

4단계 O(n log n), 수열까지 출력

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

 

14003번: 가장 긴 증가하는 부분 수열 5

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

www.acmicpc.net

마지막은 n 조건도 커지고, 정답 수열까지 출력해야 하는 문제이다. 이 문제를 풀기 위해선 2번째 문제 풀이를 응용하여 lower_bound(이진탐색)으로 찾은 인덱스 값을 따로 저장해 풀 수 있다. 마지막 출력 시 뒤에서 부터 정답 수열 길이 값과 매칭되는 인덱스 값을 순차적으로 찾으며 출력하면 된다.

 

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
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, arr[1000001], idx[1000001], ans2[1000001];
 
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d", &arr[i]);
    }
 
    vector<int> ans;
    ans.push_back(arr[0]);
    idx[0] = 0;
    for(int i=1; i<n; i++){
        if(ans.back() < arr[i]) {
            ans.push_back(arr[i]);
            idx[i] = ans.size()-1;
        } else {
            vector<int>::iterator it = lower_bound(ans.begin(), ans.end(), arr[i]);
            *it = arr[i];
            idx[i] = distance(ans.begin(), it);
        }
    }
 
    printf("%d\n", ans.size());
    for(int i = n-1, len = ans.size()-1; i>=0 && len>=0; i--){
        if(idx[i] == len){
            ans2[len] = arr[i];
            len --;
        }
    }
 
    for(int i=0; i < ans.size(); i++){
        printf("%d ", ans2[i]);
    }
    return 0;
}
 cs

 

결국 4단계 풀이 방법만 기억하고 있으면, 모두 풀 수 있다.

저작자표시

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 2407 조합  (0) 2020.09.04
LCS 최장 공통 부분 수열  (0) 2020.09.03
BOJ 4811 알약  (0) 2020.08.28
BOJ 12865 평범한 배낭  (0) 2020.08.28
BOJ 15649~15650 N과 M  (0) 2020.08.20

 

 

 

이 문제는 동적계획법(DP)으로 풀 수 있는 문제이다. 그 이유는 완전한 알약 갯수와 반쪽 짜리 알약 갯수가 주어질 때, 문자열의 경우의 수는 일정하기 때문이다. 따라서 DP는 다음과 같이 정의 할  수 있다.

dp[w][h] = 완전한 알약이 w 개 있고,  반쪽 짜리 알약이 h 개 있을 때, 문자열의 경우의 수

dp[w][h] = dp[w-1][h+1]  +  dp[w][h-1]

 

 

 

Top-Down

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef long long ll;
ll dp[33][66];
 
ll solve(int w, int h){
    if(w == 0)
        return 1;
    
    ll& ret = dp[w][h];
    if(ret != 0)
        return ret;
    
    ll s = solve(w-1, h+1);
    if(h > 0)
        s = s + solve(w, h-1);
    return ret = s;
}
 cs

 

 

Bottom-Up

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef long long ll;
ll dp[33][66];
 
// 초기화    
for(int h=1; h<=60;h++)
    dp[0][h] = 1;
dp[1][0] = 1;
 
for(int w=1; w<=30; w++){
    for(int h=0; h<=60; h++){
        dp[w][h] = dp[w-1][h+1] + (h > 0 ? dp[w][h-1] : 0);
    }
}
 cs

이 문제는 초기화만 잘 해준다면 Top-Down 방식과 코드가 큰 차이가 없이 Bottom-Up 또한 꽤 직관적인 코드가 짜여진다.

 

 

 

전체 소스 코드

 

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
#include<stdio.h>
 
int n;
typedef long long ll;
ll dp[33][66];
ll inline  max(ll a, ll b){return a>b?a:b;}
ll solve(int w, int h){
    if(w == 0)
        return 1;
    
    ll& ret = dp[w][h];
    if(ret != 0)
        return ret;
    
    ll s = solve(w-1, h+1);
    if(h > 0)
        s = s + solve(w, h-1);
    return ret = s;
}
int main(){
    // solve(30, 0);
    
    for(int h=1; h<=60;h++)
        dp[0][h] = 1;
    
    dp[1][0] = 1;
    for(int w=1; w<=30; w++){
        for(int h=0; h<=60; h++){
            dp[w][h] = dp[w-1][h+1] + (h > 0 ? dp[w][h-1] : 0);
        }
    }
 
    while(1){
        scanf("%d",&n);
        if(n==0) break;
        printf("%lld\n", dp[n][0]);
    }
    return 0;
}
 cs

 

 

 

 

 

 

저작자표시

'알고리즘 문제풀이' 카테고리의 다른 글

LCS 최장 공통 부분 수열  (0) 2020.09.03
BOJ 가장 긴 증가하는 부분 수열  (0) 2020.09.02
BOJ 12865 평범한 배낭  (0) 2020.08.28
BOJ 15649~15650 N과 M  (0) 2020.08.20
BOJ 2580 스도쿠  (0) 2020.08.20

+ Recent posts

티스토리툴바