다이나믹프로그래밍

Developer:Bird·2020년 11월 2일
0

알고리즘

목록 보기
1/17

[정의]

Time Complexity(시간복잡도)를 줄이기 위해 이미 계산했던 부분에 대하여 Cache(저장)하여 메모이제이션(memoization)하는 기법이다.

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

[예시]

(1) 피보나치함수

다음과 같이 피보나치 함수를 구하는 문제에 있어서 배열에 값을 저장하지 않고 재귀함수를 통해서 구현할때 Fib(5)을 구하기 위해서는 Fib(3)을 총두번, Fib(2)를 세번 실행하는것처럼 이미 계산했던 값들에 대해 비효율적인 작업을 실행하여야 한다. 이때 이전에 나왔던 값들에 대해서 캐시(저장)하고 있다면 Fib(1),Fib(2),Fib(3),Fib(4),Fib(5)까지 한번씩만 계산하면 된다.

[방식]

(1) Bottom Up(상향식):
for문을 통해서 구현할 수 있다.
예시의 피보나치 함수를 구할때 Bottom Up을 이용하면
Fib(1)부터Fib(2) Fib(5)까지 밑에서 부터 위로 올라가는 방식으로 구현하게된다.

cache[0]=cache[1]=1;
for(int i=2;i<=5;i++)
{
cache[i]=cache[i-1]+cache[i-2];
}

(2) Top Down(하향식):
SelfRecurrency(재귀함수)를 통하여 구현할 수 있다.
예시의 피보나치 함수를 구할때 Top Down을 이용하면
Fib(5)부터 Fib(1)까지 위에서 밑의 지점까지 내려가는 방식으로 구현하게된다.

cache[0]=cache[1]=1; //방문함
cache[2]=cache[3]=cache[4]=cache[5]=-1 //방문안함
int fib(int N){
int &res=cache[N];
if(res!=-1) return cache[N];
res=0;
return res=fib(N-1)+fib(N-2);
}
fib(5);

[활용]

(1) Greedy DP : Max,Min찾기

TopDown,BottomUp방식이 모두 사용 가능하다.
예시: 최장증가수열찾기
Bottom Up:

    for (int i = 1; i <= N; i++)
    {
        for (int j = i - 1; j >= 0; j--)
        {
            if (seq[i] > seq[j]) up[i] = max(cache[i], cache[j] + 1);
        }
    }

Top Down:

int dp(int cur)
{
int &res = up[cur];
if (res != -1)
    return res;
res = 0;
for (int i = cur + 1; i <= N; i++)
{
    res = max(res, (seq[cur] < seq[i]) + dp(i));
}
return res;
}

(2) DFS or BFS or Graph + DP

관련문제: 미로탐색 https://www.acmicpc.net/problem/17090
탐색했던 부분, 위치에 관해서 메모리제이션 할때 사용한다. 이럴경우 Bottom Up방식을 주로 사용한다.
예시: TSP외판원 순회문제

int TSP(int here, int visited)
{
        //기저 사례: 모든 도시를 다 방문했을 때는 0번 도시로 돌아가고 종료
        if (visited == (1 << N) - 1)
        {
               if (W[here][0] != 0)
                       return W[here][0];
               return INF;
        }
        //메모이제이션
        int &result = cache[here][visited];
        if (result != -1)
               return result;
        result = INF;
        //다음 방문할 도시를 전부 시도
        for (int next = 0; next < N; next++)
        {
               //이미 방문한 도시
               if (visited & (1 << next) || W[here][next]==0)
                       continue;
               int candidate = W[here][next] + TSP(next, visited + (1 << next));
               result = min(result, candidate);
        }
        return result;
}
profile
끈임없이 발전하자.

1개의 댓글

comment-user-thumbnail
2022년 8월 20일

마지막 꺼 이럴 경우 top down 방식을 주로 사용하는 거 아닌가용?

답글 달기