동적 프로그래밍 (dynamic programming)

동적 프로그래밍이란?

흔히 dp라고 불리는 이 알고리즘은, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다. 

 

어떤 상황에 사용?

dp를 사용하기 위해서는 아래 조건을 만족해야 한다.

1. 겹치는 부분 문제 (Overlapping Subproblems) : 동일한 작은 문제들이 반복하여 나타난다

2. 최적 부분 구조 (Optimal Substructure) : 부분 문제의 최적 결과값을 사용해 전체 문제의 최적 결과를 낼 수 있다

3. 단순한 부분 문제 (Simple Subproblems) : 부문제들이 j, k, l, m과 같은 몇 개의 변수로 정의될 수 있다

 

보통은 위의 1, 2번을 만족시킬 때 dp를 사용할 수 있다고 한다. 

 

분할통치법과의 관계?

공통점 : 원점 - 목표점 구조

- 원점: 문제의 초기 또는 기초 지점

- 목표점: 최종해가 요구되는 지점

 

차이점 : 문제 해결 진행 방향

- dp: 원점 => 목표점 (단방향)

- 분할통치: 목표점 => 원점 => 목표점 (양방향) (단 해를 구하기 위한 연산 진행 방향은 원점 => 목표점)

 

어떻게 사용?

1. DP로 풀 수 있는 문제인지 확인한다

2. 문제의 변수를 파악한다

3. 변수 간 관계식을 만든다

4. 메모한다

5. 기저 상태를 파악한다

6. 구현한다

 

사실상 dp를 조금 풀다 느낀 건데, dp(n)에 대한 정의를 명확히 하고, 점화식을 세우는 것이 가장 중요한 것 같다.

점화식을 세울 때는 내가 뭘 찾고 싶은 것인지. 에 대한 것을 명확히 하다 보면 금방 찾을 수 있었다.

 

처음엔 어려우니 dp(0), dp(1), dp(2)... 를 순서대로 방문하여 규칙성을 찾는 것에 적응하면 쉽다.

 

예제

1년 전에 dp를 풀다가 포기했던 문제로 dp를 복습해 보고자 한다.

 

https://www.acmicpc.net/problem/11053

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

 

 

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구한다.

수열의 크기 N (1 <= N <= 1,000)

Ai (1 <= Ai <= 1,000)

해결

먼저 우리가 구하고자 하는 것이 무엇인지 명확히 해 보자.

 

len(1) = 1

len(2) = 1 or len[1] + 1

len(3) = 1 or len[1] + 1 or len[2] + 1

...

len(n) = n번째 인덱스에서의 가장 긴 증가하는 부분 수열의 길이 = board[i] < board[n]을 만족시키며 가장 긴 수열의 길이를 가진 i에 대해 len[i] + 1 (i < n) or 1 (board[i] < board[n]인 i가 없는 경우)

 

따라서 n번째 수열에 대한 가장 긴 증가하는 부분 수열의 길이를 구하려면 0 ~ n-1 를 돌며 board[n]보다 작은 원소들 중 부분 수열의 길이가 가장 긴 길이 + 1을 저장해 주면 된다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int n, answer = 0;
int board[1001];
int len[1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> board[i];
    
    for (int i = 0; i < n; i++) {
        int ck = 0;
        for (int j = 0; j < i; j++) {
            if (board[i] > board[j] && ck < len[j]) ck = len[j];
        }
        len[i] = ck + 1;
        if (len[i] > answer) answer = len[i];
    }

    cout << answer;
}