Problem Solving/Algorithm

6. 동적 계획법 (DP)

728x90

Dynamic programming이란?

복잡한 문제를 여러 간단한 문제로 쪼개서 푸는 것

기본적으로 고등학교 때 학습하였던, 점화식을 활용하여 푸는 방법론이라고 이해해도 무방한다.

구현 방법

구현 방법은 크게 2가지가 있다.

반복분

장점
1. 빠르고 메모리 측면에서 이득을 본다.
2. DP 최적화 작용이 쉽다. (덱 DP, 세그 DP)
단점
1. 테이블을 채우는 순서를 고려해야 한다.
2. 순서가 복잡한 경우 사용하기 어렵다. (트리 DP, 비트 DP)

재귀 (Memoization을 사용)

장점
1. DP를 채우는 순서를 고려하지 않아도 되나, memoization을 사용하여 동일 반복 계산을 피한다.
2. 순서가 복잡한 경우에도 처리하기 쉬움 (트리 DP, 비트 DP)
단점
1. 반복문에 비해 느리고 메모리가 많이 든다.
2. DP 최적화 작용이 어렵다. (덱 DP, 세그 DP)

대표 문제

LCS

Let $f(i, j)$ : $A[0:i]$, $B[0:j]$ LCS length

Case1 $A[i] \neq B[j]$
$f(i, j) = max(f(i - 1, j), f(i, j - 1))$
Case2 $A[i] = B[j]$
$f(i, j) = f(i - 1, j - 1) + 1$

위 문제에서 f를 잡을 때, 2개의 parameter를 사용하였다.
정보가 문자열 A와 B, 총 2가지의 정보가 필요하므로 해당 개수만큼 잡았다고 생각해주면 된다.

추가적으로 LCS를 역추적하기 위해서는, 해당 최대값이 나오기 위한 경로를 역추적해주면 된다. LCS의 길이가 늘어나는 상황은 $A[i] = B[j]$가 유일하기 때문이다.

LIS

Let $dp[i]$ : length of LIS considering until $i$th element.
$dp[i]$ = $\underset{j < i, A[j] < A[i]}{max}dp[j] + 1$

이 문제의 경우, 증가하는 수열을 만들기 위해서 자신보다 앞에 있는 index의 LCS 정보만 가지고 있으면 충분하다. 또한 그러한 관계를 활용하여 점화식을 세워주면 된다.

추가적으로 LIS를 역추적하기 위해서는, 해당 최대값이 나오기 위한 경로를 마찬가지로 역추적해주면 된다. 앞의 index로 이동하면서 value값은 감소하면서 해당 dp의 값은 1칸씩 점진적으로 감소되게끔 하는 숫자를 찾아주면 된다.

활용

k번째 원소 찾기

대표적인 문제는 이진수 찾기이다.

잘 생각해보면 1을 넣을 수 있는 개수가 제한되어 있고, 자리수를 늘려감에 따라 추가적으로 1을 넣을 수 있는지 여부는 뒤에 1이 몇 개 존재하는지에 지배당하는 구조로 이루어져 있다. 따라서 하위 계층의 정보를 활용하여 상위 계층을 구성할 수 있는 상황이므로 DP로 풀 수 있음을 파악할 수 있다.

이때, 자리수를 늘려감에 따라 1을 몇개 썼는지 여부도 고려해야하므로 parameter를 1개 추가해주면 된다.

Let $dp[i][j]$ : number of sequence with length i that can be made using 1 j times.
$ dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]$

만약 어떠한 자리까지 고려해서 숫자를 만드는 상황에서, 최대한의 1을 활용해서 만들 수 있는 개수가 주어진 k보다 더 큰 경우에는 그 다음 자리수에 1이 무조건 들어갈 수 밖에 없다는 의미로 이해할 수 있다. 해당하는 정보를 활용해서 k번째 원소를 구해줄 수 있다. 또한 1을 사용한 상황이므로 그보다 작은 자리수부터는 사용할 수 있는 1의 개수를 1개씩 줄여나가면서 반복해주면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

ll dp[32][32]; // dp[i][j] = i번째 자리까지 고려할 때 총 소모된 1의 개수가 j인 개수

int main(void){
    memset(dp, 0, sizeof(dp));

    ll n, l, i;
    cin >> n >> l >> i;

    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;

    for(int i = 2; i <= n; i++){
        dp[i][0] = 1;
        for(int j = 1; j <= i; j++){
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }

    while(n > 0){
        ll check = 0;
        for(int i = 0; i <= l; i++){
            check += dp[n - 1][i];
        }
        if(check >= i) cout << 0;
        else{
            i -= check;
            l--;
            cout << 1;
        }
        n--;
    }
    cout << "\n";

    return 0;
}

해당 코드를 보고 대략적으로 이해하도록 하자.
맨 마지막 while문을 보면 알겠지만, 해당 index 이전 dp값에 대한 정보를 가지고 index의 값이 0인지 1인지를 추정한다는 점을 주의하도록 하자.

Tree DP

일반적으로 해당 트리에 대한 서브 트리에 대한 정보를 가지고 계속해서 상위 트리로 이동하면서 문제를 처리하는 방식을 의미한다.

대표적인 문제는 사회망 서비스이다.

모든 노드들이 정보를 받아들이기 위해서는 자신이 얼리어답터이거나 이웃한 노드가 모두 얼리어답터면 된다. 즉 주변에 있는 정보를 통해 자신이 얼리어답터가 반드시 되어야하는지가 결정되는 양상임을 쉽게 파악할 수 있다.

즉, 밑에 있는 정보를 토대로 자신이 얼리어답터이거나 얼리어답터가 되지 않기 위한 조건을 구할 수 있게 된다.

Let $dp[i][j]$ : the number cases that node $i$ satisfy j conditon (0 : early adapter, 1 : not)

Case 1 (j == 0)
$dp[i][j]$ = $\underset{y\in child(x) }{\Sigma}min(dp(y, 0)+ 1, dp(y, 1))$
Case 2 (j == 1)
$dp[i][j]$ = $\underset{y\in child(x) }{\Sigma}(dp(y, 0)+ 1)$

이때, dp에서 노드 x의 얼리어답터 유무를 개수에 포함시키지 않은 이유는 부모 노드에 의해서도 얼리어답터 여부가 결정되기 때문에 bottom up 방식으로는 바로 결정지을 수 없기 때문으로 이해하면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX_N 1000001

using namespace std;

int n;
vector<int> adj[MAX_N]; // 연결 리스트
vector<int> adj_below[MAX_N];
int visited[MAX_N]; // 방문확인
int dp[MAX_N][2];

void dp_return(int node){
    visited[node] = 1;
    for(int i = 0; i < adj[node].size(); i++){
        int to = adj[node][i];
        if(visited[to] == 1) continue;
        else{
            adj_below[node].push_back(to);
            dp_return(to);
            int min_cost_zero = 0;
            int min_cost_one = 0;
            for(int i = 0; i < adj_below[node].size(); i++){
                int to = adj_below[node][i];
                min_cost_zero += min(dp[to][0] + 1, dp[to][1]);
                min_cost_one += dp[to][0] + 1;
            }
            dp[node][0] = min_cost_zero;
            dp[node][1] = min_cost_one;

        }
    }
}


int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    memset(dp, 0, sizeof(dp));
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int n1, n2;
        cin >> n1 >> n2;
        adj[n1].push_back(n2);
        adj[n2].push_back(n1);
    }
    dp_return(1);
    cout << min(dp[1][0] + 1, dp[1][1]) << "\n";
    return 0;
}

Contents

새소식

인기 검색어