Dynamic Programming

Dynamic Programming(DP) , 동적 계획법

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

  -> 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것

  -> 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결

  * 동적계획법은 계산 횟수를 줄일 수 있다. 특히 하위 문제의 수가 기하급수적으로 증가할 때 유용

위키 (https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95)

*피보나치 수로 DP 기초 다지기

  F(0) = 0

  F(1) = 1

  F(N) = F(N-1)+F(N-2) (N>=2)

0 1 1 2 3 5 8 13 21 34 ... 로 반복되는 수로 피보나치 수를 구하는 함수는 아래와 같다.

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    else
    {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

fibonacci(5)를 호출할 경우 함수는 아래와 같이 호출되며, 그림과 같이 겹치는 호출이 생긴다.

이러한 겹치는 호출이 생기면 구한값을 저장해두고, 중복 호출 시 메모해놓은 값을 리턴한다.

코드로 구현하면 아래와 같다.

int memo[100];
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    else
    {
        if (memo[n] > 0)
            return memo[n];
 
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return memo[n];
    }
}

다이나믹 프로그래밍을 푸는 방법에는 두가지가 있다.

 1) Top-Down

 2) Bottom-Up

 일반적으로 Top-Down은 큰 문제를 작은 문제로 나눈 후 작은문제들의 문제를 풀고 큰 문제의 답을 구해는 방식이고.

Bottom-up의 경우 문제를 크기가 작은 문제부터 순차적으로 조금씩 크게 만들면서 문제를 푸는 방식이다.

fibonacci로 예시를 들면, 위의 소스는 Top-down 방식으로 구현한 것이고, 아래 소스는 Bottom-up 방식의 소스이다.

int d[100];
int fibonacci(int n)
{
    d[0] = 1;
    d[1] = 1;
    for (int i = 2; i <= n; i++) {
        d[i] = d[i - 1] + d[i - 2];
    }
    return d[n];
}

역시 DP도 문제를 많이 풀어보면서 익숙해지는 게 중요. 

먼저 아래 세문제가 DP 기초를 다지는 데 도움이 된다.

 - 1로만들기(https://www.acmicpc.net/problem/1463)

 - 2xn 타일링(https://www.acmicpc.net/problem/11726)

 - 2xn 타일링2(https://www.acmicpc.net/problem/11727)

타일채우기 풀이