문자열 문제

최단 편집 거리

코드 예제를 통해 두 문자열 간의 최소 편집 횟수를 계산합니다. 이는 삽입, 삭제, 대체 연산을 포함합니다.

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1010;
int n, m;
char strA[MAXN], strB[MAXN];
int dp[MAXN][MAXN];

int main() {
    cin >> n >> (strA + 1);
    cin >> m >> (strB + 1);

    for (int i = 0; i <= m; i++) dp[0][i] = i;
    for (int i = 0; i <= n; i++) dp[i][0] = i;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1});
            if (strA[i] == strB[j]) 
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            else 
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

가장 긴 공통 부분 수열 (LCS)

두 문자열 간 가장 긴 공통 부분 수열을 찾습니다.

#include <iostream>

using namespace std;

const int MAXN = 1010;
int n, m;
char strA[MAXN], strB[MAXN];
int dp[MAXN][MAXN];

int main() {
    cin >> n >> m >> (strA + 1) >> (strB + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (strA[i] == strB[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[n][m] << endl;
    return 0;
}

구간 동적 프로그래밍

구간 병합 예제: 돌 더미 합치기

이 코드는 주어진 길이의 구간에서 최소 비용으로 돌 더미를 합치는 방법을 보여줍니다.

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 310;
int n, sum[MAXN];
int dp[MAXN][MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = 1e8;
            for (int k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

회문 문제

주어진 문자열에서 가장 긴 회문 부분 수열을 찾습니다.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1005;
int dp[MAXN][MAXN];
char str[MAXN];

int main() {
    scanf("%s", str);
    int n = strlen(str);
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (len == 1) dp[i][j] = 1;
            else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                if (str[i] == str[j])
                    dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
            }
        }
    }
    cout << n - dp[0][n - 1] << endl;
    return 0;
}

괄호 매칭 문제

괄호 문자열의 올바른 매칭을 확인하고 최소 수정 횟수를 계산합니다.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 110;
bool isMatch(char l, char r) {
    return (l == '[' && r == ']') || (l == '(' && r == ')');
}

int dp[MAXN][MAXN];
string s;

int main() {
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++) dp[i][i] = 1;

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = 1e9;
            if (isMatch(s[i], s[j])) dp[i][j] = dp[i + 1][j - 1];
            dp[i][j] = min(dp[i][j], min(dp[i][j - 1], dp[i + 1][j]) + 1);
            for (int k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
        }
    }
    cout << dp[0][n - 1] << endl;
    return 0;
}