DP와 피보나치

    

학창시절 배운 피보나치를 떠올려보자

피보나치는 점화식으로 f(1)=f(2)=1 을 기준으로 n>2일때 f(n)=f(n-1)+f(n-2)로 표현된다.

단, 이 피보나치의 문제는 그림처럼 많은계산이 중복됨을 알 수 있다.

        

컴퓨터는 Memoization이라고하여 메모리에 중간 계산 결과를 caching(캐싱)함으로써 중복 계산을 피할 수 있다. 즉, f(n)값을 저장해놨기때문에 새로 계산할 필요가 없어서 효율적이다. 이렇게되면 동일한 피보나치 넘버를 두번 계산할 필요없이 배열에 저장된 값을 사용할 수 있다.         

        

bottom-up 방식

       

        

f(1)부터 순서대로 올라가는 방식으로써 f(8)의 값을 구한다고하면 f(6), f(7)의 값이 필요한데, 순서대로 계산했으므로 f(6), f(7)의 값은 이미 계산되어있기 때문에 그냥 더해주면된다. 즉, 가장 기본적인 값에서부터 출발하여 순차적으로 올라오는 방식이다.

그리고 피보나치는 1차원 배열방식이고 DP는 2차원 배열방식임을 기억해두자.

    

이항계수

고등학교 때 배운 순열과조합 과목을 떠올려보자.

        

       

nCk(n개 중 k개를 선택하는 경우의 수)를 구하는 공식은 위와 같다.

하지만 이 공식을 사용하는 것은 수학적으로는 문제가 없지만 컴퓨터로 계산시에는 문제가 생긴다.

    

일반적으로 컴퓨터는 팩토리얼(!) 계산이 너무 크기때문에 기본 데이터타입이 표현할 수 없는 오버플로우가 발생한다.

    

    

    

따라서 컴퓨터는 위의 공식을 활용한다.

    

공식을 약식으로 설명하면 n이 줄어들거나 n과 k 둘다 줄어들거나하는데, k가 가만히 있고 n가 줄어든다면 n과k가 가까워지면서 언젠가 n과 k가 같아질 것이고 n, k 둘이 동시에 줄어든다면 k가 0에 도달한다는 뜻이다.

    

Memoization을 통해서 배열에 저장할 때 n과 k 두가지 값이므로 이차원배열로 표현할 수 있다.

    

int binomial(int n, int k)
{
    if(n == k || k ==0)
        return 1;
    else if (binom[n][k] > -1) /* 배열 binom이 -1로 초기화되어 있다고 가정 */
        return binom[n][k];
    else {
        binom[n][k] = binomial(n-1, k) + binomial(n-1, k-1);
        return binom[n][k];
        }
}    

    

위의 코드는 n 이 k이거나 k가 0 이면 1을 리턴하고, 배열 binom이 -1로 초기화되어 있다고 가정하고 binom[n][k]가 -1이 아니라면 이미 계산되어 배열에 저장되어있다는 뜻이므로 바로 리턴해준다. 그렇지않다면 순환식을 이용해서 binomial값을 계산하고 binom[n][k] 배열에 저장하고 리턴해준다.

    

    

DP bottom up 방식

int binomial(int n, int k)
{
    for (int i=0; i<=n; i++) {
        for (int j=0; j<=k && j<=i; j++) { //j가 n,k 초과의값들을 굳이 계산할 필요가없다.
            if (k==0 || n==k)
                binom[i][j] = 1;
            else
                binom[i][j] = binom[i-1][j-1] + binom[i-1][j];
        }
    }
    return binom[n][k];
}

    

DP bottom up 방식은 2차원 배열방식임으로 어디에서 출발할지 애매하다.

이는 기본에서 시작해서 원하는 값으로 올라온다고 생각하자.

위 코드에서 binom[i][j] = binom[i-1][j-1] + binom[i-1][j]; 순환식을 이용해서 계산할 때 좌항을 구하기 위해서 우항이 먼저 계산되어지는 순서를 bottom up방식으로 생각하면 되겠다.

    

    

참고영상

[알고리즘] 제18-1강 동적계획법 (Dynamic Programming)

    

간단한 문제풀이

간단한 문제풀이로 감을 익혀보자. 참고로 언어는 파이썬을 사용했다.

    

    

네트워크 선자르기(Bottom-Up, Top-down) -python

    

    

bottom-up 풀이

#네트워크 선 자르기 bottom-up
n=int(input())
dy=[0]*(n+1) #파이썬은 리스트로 배열을만든다.
dy[1]=1
dy[2]=2

for i in range(3, n+1):
    dy[i]=dy[i-1]+dy[i-2]

print(dy[n])

    

    

    

    

    

    

    

Top-Down:재귀, 메모이제이션 풀이

#네트워크 선 자르기 Top-Down:재귀, 메모이제이션
def DFS(len):
    if dy[len]>0:  # 메모리제이션으로 가지커트(초기화 0보다 크면 바로 호출!)
        return dy[len]
    if len==1 or len==2: #종착지
        return len
    else:
        dy[len]=DFS(len-1)+DFS(len-2) #순환식
        return dy[len]

n=int(input())
dy=[0]*(n+1) #리스트(배열) 생성
print(DFS(n))