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

github : https://github.com/junho0956/Algorithm/blob/master/1958/1958/%EC%86%8C%EC%8A%A4.cpp

 

LCS 의 개념을 정리한 포스팅입니다.

LCS : https://junho0956.tistory.com/39?category=868069

 

LCS2보다 오히려 쉬운 문제입니다. LCS의 개념을 안다는 가정하에말이죠

2차원에서 3차원으로 늘어난 것 뿐이고, 3중포문이지만 100*100*100 에 if문 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
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int dp[101][101][101];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    string fs, ss, ts;
    cin >> fs >> ss >> ts;
 
    for (int i = 0; i < fs.length(); i++) {
        for (int j = 0; j < ss.length(); j++) {
            for (int k = 0; k < ts.length(); k++) {
                if (fs[i] == ss[j] && ss[j] == ts[k]) dp[i + 1][j + 1][k + 1] = dp[i][j][k] + 1;
                else dp[i + 1][j + 1][k + 1] = max(dp[i][j + 1][k + 1], max(dp[i + 1][j][k + 1], dp[i + 1][j + 1][k]));
            }
        }
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2636번 치즈  (0) 2020.02.13
BOJ 13711번 LCS 4  (0) 2020.02.12
BOJ 9252번 LCS2  (0) 2020.02.12
BOJ 9251번 LCS  (0) 2020.02.12
BOJ 5502번 팰린드롬  (0) 2020.02.12

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

github : https://github.com/junho0956/Algorithm/blob/master/9252/9252/%EC%86%8C%EC%8A%A4.cpp

 

LCS 기본개념

LCS : https://junho0956.tistory.com/39?category=868069

 

LCS 의 스트링을 알기위해서는 DP 가 값이 채워지는 형태를 관찰하시면 됩니다.

if( str1[i] == str2[k] ) 이 되는 지점에서 i-1, k-1 에서 +1 값을 하는 형태입니다.

 

DP 의 형태를 자세히 관찰해보면 같은 값을 이루는 형태가

 

00000000

01111111

01111222

01222233

01222234

01222234

 

이런식으로 이루어지게 될것입니다.

여기서 알 수 있는 것은 값이 i-1, k-1 에서 +1 했을 때 바뀌는 지점은 분명 공통으로 단어를 가지고있는 부분이 된다는 뜻이고, 위의 숫자의 배열들을 봤을 때 그 특정 지점을 알기 위해서는 자신을 기준 i-1 또는 k-1 한 부분이 같은 값이면

어디에서 값이 바뀐 것인지 알 수 없기 때문에 그 같은 지점으로 이동하면서 탐색을 해주면 되는 것입니다.

i-1, k-1 둘다 값이 다른 값이 +1로 갱신되는 지점이 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
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
 
int dp[1001][1001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    string str1, str2;
    cin >> str1 >> str2;
 
    for (int i = 0; i < str1.length(); i++) {
        for (int k = 0; k < str2.length(); k++) {
            if (str1[i] == str2[k]) dp[i + 1][k + 1] = dp[i][k] + 1;
            else dp[i + 1][k + 1] = max(dp[i + 1][k], dp[i][k + 1]);
        }
    }
 
    cout << dp[str1.length()][str2.length()] << "\n";
 
    // backtracking
    // dp가 덮히는 특성상 끝지점을 기준 위->왼쪽로 가면서 스트링 길이에 맞게 계속 이동한다
 
    stack<char> s;
    int cnt = dp[str1.length()][str2.length()];
    int y = str1.length();
    int x = str2.length();
    while (cnt) {
        // 현재 dp값이 cnt와 같을때 왼쪽과 위를 확인
        if (dp[y][x] == cnt) {
            if (dp[y][x - 1] == cnt) x--;
            else if (dp[y - 1][x] == cnt) y--;
            // 같다면 위로 한칸 이동한다
            else s.push(str1[y - 1]), y--, cnt--;
        }
    }
 
    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 13711번 LCS 4  (0) 2020.02.12
BOJ 1958번 LCS 3  (0) 2020.02.12
BOJ 9251번 LCS  (0) 2020.02.12
BOJ 5502번 팰린드롬  (0) 2020.02.12
BOJ 3793번 Common Subsequence  (0) 2020.02.12

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

github : https://github.com/junho0956/Algorithm/tree/master/9251

 

LCS에 대한 설명을 포스팅해놓았습니다. 참고하시면됩니다

LCS : https://junho0956.tistory.com/39?category=868069

 

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 <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int dp[1001][1001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    string str1, str2;
    cin >> str1 >> str2;
 
    for (int i = 0; i < str1.length(); i++) {
        for (int k = 0; k < str2.length(); k++) {
            if (str1[i] == str2[k]) dp[i + 1][k + 1] = dp[i][k] + 1;
            else dp[i + 1][k + 1] = max(dp[i + 1][k], dp[i][k + 1]);
        }
    }
 
    cout << dp[str1.length()][str2.length()];
    return 0;
}
 
 
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1958번 LCS 3  (0) 2020.02.12
BOJ 9252번 LCS2  (0) 2020.02.12
BOJ 5502번 팰린드롬  (0) 2020.02.12
BOJ 3793번 Common Subsequence  (0) 2020.02.12
BOJ 1365번 꼬인 전깃줄  (0) 2020.02.11

BOJ : https://www.acmicpc.net/problem/5502

github : https://github.com/junho0956/Algorithm/blob/master/5502/5502/%EC%86%8C%EC%8A%A4.cpp

 

팰린드롬과 관련된 가장 기본이 되는 문제중 하나입니다.

하나의 스트링을 가지고 팰린드롬이 되기 위해 필요한 단어의 최소 갯수를 알기 위해서는

LCS(https://junho0956.tistory.com/39?category=868069) 에 대한 개념을 알아야합니다.

 

팰린드롬의 특성상 주어진 스트링과 이 스트링을 reverse (뒤집은) 스트링의 공통된 최장 부분문자열의 길이를 알고 있다면 답을 구할 수 있습니다.

 

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
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int dp[5001][5001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int n; string str, restr;
    cin >> n >> str;
    restr = str;
    reverse(restr.begin(), restr.end());
 
    int len = str.length();
    for (int i = 0; i < len; i++) {
        for (int k = 0; k < len; k++) {
            if (str[i] == restr[k]) dp[i + 1][k + 1] = dp[i][k] + 1;
            else dp[i + 1][k + 1] = max(dp[i + 1][k], dp[i][k + 1]);
        }
    }
 
    cout << n - dp[len][len];
    return 0;
}
 
 
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 9252번 LCS2  (0) 2020.02.12
BOJ 9251번 LCS  (0) 2020.02.12
BOJ 3793번 Common Subsequence  (0) 2020.02.12
BOJ 1365번 꼬인 전깃줄  (0) 2020.02.11
BOJ 3745번 오름세  (0) 2020.02.11

+ Recent posts

티스토리툴바