최장 공통 부분 수열 (Longest Common Subsequence)

이전 문제와의 주요 차이점은 부분 수열 내 원소가 연속적이지 않아도 된다는 점입니다. 이로 인해 dp[i][j] 값은 왼쪽과 위쪽에서 올라오는 두 가지 경로를 고려해야 합니다.

class Solution {
public:
    int longestCommonSubsequence(string& first, string& second) {
        vector<vector<int>> dp(first.size() + 1, vector<int>(second.size() + 1, 0));
        
        for (int idx1 = 1; idx1 <= first.size(); ++idx1) {
            for (int idx2 = 1; idx2 <= second.size(); ++idx2) {
                if (first[idx1 - 1] == second[idx2 - 1]) {
                    dp[idx1][idx2] = dp[idx1 - 1][idx2 - 1] + 1;
                } else {
                    dp[idx1][idx2] = max(dp[idx1 - 1][idx2], dp[idx1][idx2 - 1]);
                }
            }
        }
        
        return dp[first.size()][second.size()];
    }
};

겹치지 않는 선 최대 개수 찾기

두 배열 간에 겹치지 않는 선을 최대한 많이 그릴 수 있는 경우는, 같은 값을 갖는 원소들의 상대 순서가 유지되는 경우와 동일합니다. 즉, 이는 두 문자열의 최장 공통 부분 수열 문제로 변환 가능합니다.

class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        vector<vector<int>> memo(A.size() + 1, vector<int>(B.size() + 1, 0));
        
        for (int i = 1; i <= A.size(); ++i) {
            for (int j = 1; j <= B.size(); ++j) {
                if (A[i - 1] == B[j - 1]) {
                    memo[i][j] = memo[i - 1][j - 1] + 1;
                } else {
                    memo[i][j] = max(memo[i - 1][j], memo[i][j - 1]);
                }
            }
        }
        
        return memo[A.size()][B.size()];
    }
};

연속된 부분 배열의 최대 합

현재 요소가 양수인 경우만 누적합을 계속하는 그리디 접근은 전체 최댓값을 보장하지 못합니다. 따라서 동적 계획법으로 각 위치에서의 최대 부분합을 저장합니다. 상태 전이는 두 가지 중 큰 값을 선택:

• 이전까지의 합에 현재 요소를 더하기
• 현재 요소부터 새로운 구간 시작하기

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        vector<int> state(nums.size());
        state[0] = nums[0];
        int globalMax = state[0];
        
        for (int i = 1; i < nums.size(); ++i) {
            state[i] = max(state[i - 1] + nums[i], nums[i]);
            globalMax = max(globalMax, state[i]);
        }
        
        return globalMax;
    }
};

하위 수열 여부 판단

편집 거리 문제의 기초 단계입니다. 여기서는 dp[i][j]를 "첫 번째 문자열의 인덱스 i-1까지"와 "두 번째 문자열의 인덱스 j-1까지"의 공통 부분 수열 길이로 정의하여 초기화를 간단하게 처리합니다.

class Solution {
public:
    bool isSubsequence(string& sub, string& target) {
        vector<vector<int>> dp(sub.size() + 1, vector<int>(target.size() + 1, 0));
        
        for (int i = 1; i <= sub.size(); ++i) {
            for (int j = 1; j <= target.size(); ++j) {
                if (sub[i - 1] == target[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i][j - 1]; // 왼쪽에서 복사
                }
            }
        }
        
        return dp[sub.size()][target.size()] == sub.size();
    }
};