DP 2차시 : LIS, LCS, Knapsack, 토글링

1. LIS

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

boj.kr/11053 문제를 보면서 설명하겠습니다.

dp[i] : i번째 원소가 마지막인, 가장 긴 증가하는 부분 수열

dp[i] = max(dp[j]) + 1
단, arr[j] < arr[i] for all j < i

즉, dp[i] = i보다 앞에 있는 원소들 중에 arr[i]보다 작은 원소 중 가장 큰거 + 1

#include <iostream>
using namespace std;
int dp[1000];
int arr[1000];
int main(){
    int N; cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }

    int res=-1;

    for(int i=0; i<N; ++i){
        dp[i] = 1; // 기본값 설정

        for(int j=0; j<i; ++j){
            if(arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        res = max(res, dp[i]);
    }
    cout << res << '\\n';
}

연습 문제

2. LCS

Longest Common Subsequence

최장 공통 부분 문자열을 어떻게 구할 수 있을까요?