동적 계획법(DP) 1 (11053 가장 긴 증가하는 부분 수열 LIS)

DP란 다이나믹 프로그래밍의 약어이다. 한국어로 동적 계획법이라고 말한다.

동적 계획법은 어떠한 복잡하거나 큰 문제를 간단하고 작은 문제로 나누어서 푸는 알고리즘 설계 기법이다.

복잡한 문제가 같은 부분이 반복되는 부분 구조와 최적의 부분 구조를 가지고 있을 때 여러 개의 부분 문제로 나누어 설계하여 풀 수 있다.

그래서 일반적으로 부분 구조를 통해 점화식을 만들고 Bottom-Up 방식과 Top-Down(재귀)  방식을 통하여 전체 문제를 해결한다.

이 동적 계획법의 핵심 기법은 메모리제이션이다. 메모리제이션은 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 

그래서 DP 배열을 만들어서 그 값들을 미리 저장해놓은 다음 다시 동일한 계산이 필요한 부분 문제를 호출하였을 때 저장된 값을 바로 불러와 사용할 수 있도록 한다.

 

백준의 DP 문제를 통해 설명해보겠다.

1. 11503 가장 긴 증가하는 부분 수열

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

이 문제는 알고리즘에서 대표적인 문제인 LIS(Longest Increasing Subsequence) 문제이다.

수열이 주어졌을 때 가장 긴 증가하는 부분 수열을 구하는 문제이다.

이 문제에서 원하는 답은 가장 긴 증가하는 부분 수열의 길이를 구하는 것이다.

그렇다면 우리가 원하는 해는 각 부분 수열의 길이의 최대값이다.

최댓값을 구하기 위해서는 무조건 1번째 수열의 값부터 다 포함하는 게 이득이다. 그리고 구해놓은 값을 다시 구하는 경우를 막기 위해 메모리제이션을 사용하여 길이를 저장해놓을 배열을 만든다.

그럼 이제 이 배열의 인덱스 별 값은 i번째를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이라고 정의하자.

D[i] = i번째 원소를 마지막으로 하는 LIS의 길이

그렇게 되면 i < j이고 A[i] < A[j] 일 경우 D[j]=max(D[i] + 1) (1 <= i < j )가 된다.

따라서 반복되는 부분 구조와 점화식의 결과가 최적의 구조를 가지므로 DP를 이용하여 문제를 풀 수 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    vector<int> d(n);
    for (int i=0; i<n; i++) {
        d[i] = 1;
        for (int j=0; j<i; j++) {
            if (a[j] < a[i] && d[j]+1 > d[i]) {
                d[i] = d[j]+1;
            }
        }
    }
    
    cout << *max_element(d.begin(),d.end()) << '\n';
    return 0;
}