Dynamic programming

다이나믹 프로그래밍은 이름처럼 문제 해결과정을 역동적으로 진행해 나가는 알고리즘 풀이 방식이다.

예를들어, divide and conquer 방식의 경우 문제의 크기를 줄여나가면서 그 문제를 정복해 나가며 합치는 과정을 진행한다.

 

하지만! 다이나믹 프로그래밍은 단순히 문제의 크기를 나누어 가는 것이 아니라, 중복된 부분에 대한 효율적인 처리 방법에 대해서 고민한다.

 

어떤 때에 이 방식을 사용할 수 있을까?

1. 최적부분구조가 있을 때
2. 중복된 부분이 있을 때.

 

최적 부분 구조란 부분문제의 '최적의 답'을 이용해 전체 문제의 '최적의 답'을 찾을 수 있는 구조이다. 

 

예를들어 피보나치의 경우 전체 큰 문제를 계속 나눠가며 그 값들을 합쳐 올라가는데, 이 나누어진 값들을 최적부분구조라고 한다.

 

*divide가 된다면, 최적부분구조가 된다고 생각하면 될 것 같다!!

 

그런데..! 중복된 부분의 계산에 대해선 조금 다르다.

 

문제의 해결방식에서 중복에 대한 관점은 두가지가 존재한다.

1. 단순이 같은 것이 반복되는 경우
2. 같은 것이 반복되나 서로 독립적으로 시행되는 경우

 

여기서 우리가 주목해야 하는 부분은 1. 이다. 2. 의 경우 (merge sort를 할 때가 이에 해당한다.)는 중복된 문제가 아니라 반드시 시행해야 하는 부분이다.

 

 

그러면 어떻게 중복된 부분에 대한 계산을 효율적으로 처리할 수 있을까?

 

Memorization

큰 문제에서 작은 문제로 내려가면서 중복된 계산은 '한 번만' 계산 후 메모하는 것이다. (Top-down 방식)

 

피보나치 문제가 있다면, 

 

fib(1) : 1

fib(2) : 1

fib(3) : 2

fib(4) : 3

..

..

..

이런 식으로 값들을 cache에 저장해 놓고 값이 있으면 단순히 값을 불러온다.

 

 

Tabulation

작은 문제에서 큰 문제로 올라가면서 계산을 쭉 해나가며 표에 정리하는 것이다. (Bottom-up 방식)

 

fib(6)을 구하려면, fib(1)~fib(5)까지 표에 정리해서 계산 후 이 값들을 이용해 결과 값을 도출한다.

 

 

방식의 차이

큰 문제에서 작은 문제로 가는 것은 문제 해결을 재귀적으로 해결해 나갈 수 있다.

작은 문제에서 큰 문제로 가는 것은 반복문을 이용해 문제를 해결할 수 있다.

이러한 큰 차이점 때문에 두 방식에 명확한 장단점이 존재한다.

Memo 장점 : 필요한 것만 계산하기 때문에 불필요한 계산이 필요 없다.
Memo 단점 : 재귀적 방식을 사용하기 때문에 CallStack이 너무 많이 쌓여 에러가 발생할 수 있다.

Tabu 장점 : 반복적 방식을 사용하기 때문에 CallStack 오류를 걱정할 필요가 없다.
Tabu 단점 : 불필요한 계산을 해야하는 경우가 생길 수 있다. 

Tabulation의 최적화

Table에 모든 값을 저장하기에 메모리 공간이 부족할 수 있다.
따라서 가능하다면, 최대한 적은 수의 변수를 지정해서 이를 update하는 방식으로 진행해 나가면 좋다.

 

 

피보나치-Momorization

def fib_memo(n, cache):
    if n < 3 : 
        return 1
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
    
    return cache[n]
    
def fib(n):
    fib_cache = {}
    
    return fib_memo(n, fib_cache)

 

Memorization 방식은 재귀적 방식을 사용하기에 Basecase와 Recursivecase 설정이 중요하다.

 

1. n<3 : 피보나치의 base case로서 1을 return

2. cache에 이미 누군가 구해놓은 값이 있다면 이 값을 가져온다.

3. basecase도 아니고, 누군가 cache에 값을 구해놓지도 않았다면...! 

• cache에 값을 재귀적으로 불러와 초기화를 시켜준다.

 

피보나치 - Tabulation

def fib_tab(n):
    cache = [1,1]
    for i in range(2,n):
        cache.append(cache[i-1] + cache[i-2])
    return cache[n-1]

 

위에서 우리가 말했듯이 tabulation 방식은 아래에서 위로! 진행한다고 햇으니, 그냥 다 구해버리면 된다! 

별거없다.

 

def fib_optimized(n):
    current = 1
    previous = 0
    for i in range(1, n):
        current, previous = current+previous, current
    return current

대신에 리스트를 쓰면 O(n)의 공간복잡도를 가지므로 이런식으로 값을 처리하면 공간복잡도가 O(1)이 된다.

(메모리 공간 차지를 줄일 수 있다는 말!)

 

 

새꼼달꼼 장사

• 최적 부분 구조 분석

예를들어 5개를 판매한다고 해보자. 그런데 4개 1개를 파는게 더 많은 이윤이 있을 수 있고, 3개 2개를 파는게 더 큰 이윤을 얻을 수 있다고 하면, 우리는 5개, 4개1개, 3개2개의 경우를 생각해봐야하고, 이렇게 문제의 크기를 줄여서 계속 생각해 나가야 하므로 이 문제는 최적부분구조가 있다고 할 수 있다.

 

• 중북된 부분 계산

5개를 3개 2개로 나누었다고 생각해보자.

3개는 2개 1개,

2개는 1개 1개,

위의 2개는 1개 1개, 

이런식으로 쭉 나누어 나갈 수 있다. 즉 우리는 중복된 계산을 줄이는 방식을 택할 수 있다.

 

따라서 이 문제는 최적부분구조가 존재하며 효율적으로 변경시킬 수 있는 중복된 부분이 존재하므로

다이나믹 프로그래밍을 통해 해결할 수 있다는 결론을 얻을 수 있다.

 

def max_profit_memo(price_list, count, cache):
    if count <= 1 : 
        cache[count] = price_list[count]
        return cache[count]
    if count in cache:
        return cache[count]
   
    if count < len(price_list):
        profit = price_list[count]
    else:
        profit = 0
    
    for i in range(1,(count//2) + 1):
        profit = max(profit, max_profit_memo(price_list,i, cache) + max_profit_memo(price_list, count-i, cache))
        
    cache[count] = profit
    
    return profit
    
    
    
    
def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)

1. base case : 1개를 사거나 0개를 사는 경우는 다른 값과 비교할 필요가 없으므로 그대로 cache에 값을 넣어주고 리턴해주면 된다.
2. recursive case를 보기 전에 cache에 값이 있는지 확인한다.
3. 그리고 나서 사려는 수가 가격 리스트의 길이보다 큰지 작은지 판단하여 작다면 한명에게 모두 파는 경우를 '일단' cache에 넣어주고 count가 그 값보다 크면 '일단' profit = 0 을 넣어준다.
4. 그리고 반복적으로 케이스를 돌려가며 최대값을 구해준다.
5. 최신화된 profit을 cache에 넣어주고 그 값을 리턴해준다!

 

 

 

def max_profit(price_list, count): 
    profit_table = [0]
    
    for i in range(1, count+1):
        if i < len(price_list):
            profit = price_list[i]
        else:
            profit = 0
        for j in range(1, i//2 + 1):
            profit = max(profit, profit_table[j] + profit_table[i-j])
        profit_table.append(profit)
    return profit_table[count]

 

tabulation 방식은 작은 부분부터 올라가는 방식이라고 했었다. 그래서 처음부터 끝까지 table의 정보를 갱신해주기 위해 전체 적으로 for문을 한 바퀴 돌아준다.

 

그러고나서, i 가 가격리스트보다 길이가 긴지 짧은지 알아보아야한다.

짧다면, 일단 값을 대입해주고, 길다면, 일단 0을 넣어준다.

 

그리고 값을 비교해주면서 profit을 갱신해주고, 마지막에 나온 최대 값을 테이블에 넣어준다.

 

 

 

---

막상 코드를 작성하고 보면 별거 아닌 문제들이지만 생각하는데 어려웠고 고민이 많이 되었던 문제들이다. 

계속 복습하면서 방식을 익혀야겠다.

 

2021-10-24