DP ( Dynamic Programming, 동적 계획법 )

DP란?

• Dynamic Programming. 동적 계획법
• 하나의 문제를 한 번만 풀도록 하는 알고리즘
• 한 번 푼 문제를 여러번 다시 푸는 비효율을 방지할 수 있다.

          - 그렇기에 시간 절약이 가능하다.

          - problem을 sub-problem으로 잘게 쪼갠 뒤 sub-problem중 이미 풀었던 문제는 계산을 하지 않고 값을 불러오기만 하면 된다.

• DP에서 값을 불러오기 위해 memoization이 쓰인다. (기억해두었다가 값 불러오기)
• memoization : 이미 계산했던 값은 배열에 저장했다가 나중에 필요할 때 값 반환하기
• 알고리즘 문제에서는 DP를 적용할 때 무엇이 problem이고 이를 어떻게 sub-problem으로 나누는 지 정의하기가 어렵기 때문에 이 연습을 많이 해주어야 한다.

 

 

Fibonacci

개념만 보고 다 이해할 수 있는가? DP 개념을 가장 잘 이해하고 적용할 수 있는 피보나치 수열로 예를 들어 보자.

 

F[n] = F[n-1] + F[n-2]   : 피보나치 수 점화식

 

피보나치 수를 구하는 것을 코드로 나타내보자.

def f(n):
    if n == 1 : return 0
    elif n == 2 : return 1
    else:
        ans = f(n-1) + f(n-2)
    return ans

첫 번째는 0이고, 두 번째는 1이다. 

그리고 재귀적으로 f(n)을 f(n-1)과 f(n-1)로 나누어서 두 가지 값을 계속 구해주면서 이 값을 반환하는 코드이다.

 

이 코드의 문제점이 있다. 계산이 너무 오래 걸려서 비효율적이고 수가 커지면 계산하는 데에 너무 오래 걸려서 값을 반환 못 할 수도 있다

f(15)번째 수를 구한다고 해보자

15번째 수를 구하기 위해선 14번째 수와 13번째 수가 필요하다.

(왼쪽) 14번째 수를 구하기 위해선 13번째 수와 12번째 수가 필요하다.

(오른쪽) 13번째 수를 구하기 위해선 12번째 수와 11번째 수가 필요하다.

 

한 단계씩 밑으로 내려갈 수록 계산해야 하는 가지 수가 2배씩 커진다. 

만약 n의 수를 구해야 한다면 총 2^(n)가지의 계산을 해야 한다는 말이다. 얼마나 비효율적인가?

바로 여기서 DP를 통해 효율적으로 구할 수 있다.

 

- 하나의 문제를 한 번만 풀도록 한다.

위 사진에서 색깔이 같은 거는 중복되는 값들이다. 이 값들이 필요할 때마다 계산으로 구하는 게 아니고 값을 저장했다가 반환해오자.

 

-problem을 sub-problem으로 잘게 쪼갠다.

problem(15)을 구하기 위해 sub-problem(14)와 sub-problem(13)으로 나누고 problem(14)와 problem(13)을 구하기 위해 sub-problem(13, 12, 11)을 구하고 ...

 

- memoization by for문 

배열에 이미 구했던 수들을 저장하자. 없다면 수열에 추가해주고. 그래서 배열에 있는 값들은 그냥 반환하기만 하면 된다.

def f(n):
    if n == 1 : 
        return 0
    elif n == 2 : return 1
    fib_array = [0,1]
    for i in range(2,n+1):
        num = fib_array[i-1]+fib_array[i-2]
        fib_array.append(num)
    return fib_array[n-1]

 

 

for문을 이용하여 밑에서부터 (bottom up 방식) 수열에 값을 추가해나가면서 원하는 값을 반환하는 방식이다.