동적 계획법

동적 계획법이란?

문제를 여러개의 작은 문제들로 나누고 그 작은 문제들의 해답을 이용하여 원래 문제의 답을 도출함

 

동적 계획법 조건

1. 구하고자 하는 문제를 subproblem으로 쪼갤 수 있어야 함

2. subproblem의 조합으로 구하고자 하는 problem 값을 도출할 수 있어야함

 

방식

1. bottom-up 방식

for 반복문으로 실행한다.

배열에 값을 저장하여 기존 배열의 값을 조합하여 구하고자 하는 값을 구함

ex)

#include <bits/stdc++.h>
using namespace std;
int dy[50];
int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    dy[1] = 1;
    dy[2] = 2;
    for(int i=3; i<=n; i++) {
        dy[i] = dy[i-2] +dy [i-1];
    }
    cout << dy[n];
    return 0;
}

위 문제 풀이 방식

bottom up 방식

즉 규칙성 발견이 중요하다!!

4m를 자르는 경우 --> 3m 자르는 경우 + 2m 자르는 경우

why? 자를 수 있는 길이가 1m, 2m 이기 때문이다. 1m,2m로 밖에 못자르기 때문에

크게 분류했을 때 (1)2m +2m로 자르는 경우와 (2) 3m+ 1m로 자르는 경우로 나뉠 수 있다.

그런데 (1)에서 앞 2m를 자르는 경우의 수는 dy[2]이다 그리고 (2)에서 앞의 3m를 자르는 경우는 dy[3]이다.

따라서 동적 계획법을 사용할 수 있다.

 

bottom up 방식이기 때문에 for 반복문으로 순차적으로 dy에 접근하여 값을 배정한다.

 

 

2. top-down 방식

역순으로 접근하는 방식이다. 문제를 동적계획법으로 접근하는 방식은 위와 같으나

이 방식은 재귀적으로 접근한다.

재귀 + 메모이제이션

#include <iostream>
using namespace std;

int dy[101];
int DFS(int n) {
    if(dy[n] > 0) return dy[n];
    // 만약 이미 값이 있다면 cut(실행 횟수 줄여야함)
    if(n==1 | n==2) return n;
    else {
        return dy[n] = DFS(n-1) + DFS(n-2);
    }
}

int main(){
    int n;
    cin >> n;
    cout << DFS(n)<< endl;
}

**메모이제이션

역순으로 접근하기 때문에 이미 dy에 저장한 값을 또 구하는 일을 없애야 한다.

그래야 효율성이 업그레이드 된다.

if(dy[n] >0) return dy[n] 해당 코드가 메모이제이션 된 부분을 가져와서 불필요한 계산을

cutting한다.