동적계획법(Dynamic Programming)

Dynamic Programming이란?!

특정 값을 얻기 위해 매번 같은 결과를 반환하는 연산을 굳이 반복해서 수행한다면 문제를 효율적으로 해결할 수 없다.(재귀함수). 한 번 계산한 결과를 재활용하는 방식

Dynamic Programming 조건

1) 최적 부문 구조 (Optimal Substructure)

- 부문 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것

ex) 

피보나치 5번째의 수, fib(5)..(1,1,2,3,5..) 를 구한다고 했을 때 fib(3)과 fib(4)

2) 중복되는 부분 문제(Overlapping Subproblems)

- fib(7)을 알아내기 위해, fib(5)를 2번씩이나..fib(4)를 3번씩이나..구하는것

 

재귀함수(Recursive Function) vs 동적계획법(Dynamic Programming) 

 

재귀함수로 피보나치를 구현

# 재귀함수로 피보나치를 구해보자 

def solution(n):
    answer = 0
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return solution(n-1) + solution(n-2)

solution(10) # 55

f3이 3번이나 호출되었다(비효율)

 

Dynamic Programming으로 피보나치를 구현

• 1) 탑 다운(Top-Down, 하향식) 방식: 가장 큰 문제부터 시작하여 작은 문제 순으로 답을 찾아가는 방식으로, 주로 재귀 함수 활용
• 2) 바텀 업(Bottom-Up, 상향식) 방식: 가장 작은 문제의 답부터 찾아가는 방식으로, 주로 반복문 활용

탑 다운 방식보다 바텀 업 방식을 활용했을 때 다이나믹 프로그래밍의 성능이 좋다

다이나믹 프로그래밍을 구현한다고 하면 일반적으로 바텀 업 방식

 

# Top-Down   
# 한계점?!
- 재귀함수를 사용하기 때문에, *오버헤드(ovehead)가 발생

m = [0] * 100 

def solution(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if m[n] != 0:
        return m[n]     
    m[n] = solution(n-1) + solution(n-2)
    return m[n]
  
solution(10)

* 오버헤드(overhead)란?

오버헤드란 어떤 연산을 수행하기 위해 필요한 간접적인 시간 또는 메모리 등을 말합니다. 예를 들어, A라는 연산을 처리하기 위해 7초가 소요되고 안정성 등을 위해 추가적으로 B라는 처리까지 수행하는 데 10초가 걸렸다고 하죠. 그렇다면 여기서 오버헤드는 3초가 됩니다. 나아가, 만약 B라는 처리 효율을 개선하여 A와 B를 처리하는데 8초가 걸렸다면, 2초의 오버헤드를 단축시켰다고 말할 수 있습니다.

# bottom-up
# bottom-up 방식에서 결괏값을 저장해 두는 리스트를 DP 테이블이라고 한다.

m = [0] * 100 
m[0] = 0
m[1] = 1  

def solution(n):
    for i in range(2, n+1):
        m[i] = m[i-1] + m[i-2]         
    return m[n]
    
solution(10)

Dynamic Programming 구현 방식

1) Memoization(Top-down)

- 중복되는 계산은 한 번만 계산 후에 저장 해 놓고 필요할 때 마다 꺼내쓰는 방법

- 재귀를 기반으로 코드를 작성한다

def fib_memo(n, cache):
    # 코드를 작성하세요.
    if n == 1 or n ==2:
        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):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}

    return fib_memo(n, fib_cache)


# 테스트
print(fib(10))
print(fib(50))
print(fib(100))

2) Tablulation(bottom-up)

- 가장 작은 문제의 답부터 찾아가는 방식으로, 주로 반복문 활용

-  for 반복문으로 코드를 작성한다 

 

def fib_tab(n):
    # 코드를 작성하세요.
    # 계산된 피보나치 수를 저장시켜 놓을 표(table)
    fib_table = [0,1,1]
    for i in range(n+1):
        if i >=3: 
            number = fib_table[i-1] + fib_table[i-2]
            fib_table.append(number)
    return fib_table[n]      
    

# 테스트
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))

memozation 과 Tabulation 공통점 
- 둘다 중복되는 부문 문제의 비효율을 해결 

 

memozation 문제점 
- memo는 재귀를 사용하기 때문에  stack이 쌓이고 오류가 날 수 있따 

 

tabulation 은 반복문을 사용하기 떄문에 그럴 위험이 X 
하지만 tabluation은 테이블 형태로 첫번째 값부터  채워나가는 것이기 때문에 
필요 없는 값도 구한다 

- 시간복잡도: O(n) 
- 공간복잡도: O(n) 

=> 따라서 이러한 문제점을 해결하기 위해서 가장 최근 2개의 값만 사용하면은 된다?!
사용하는 메모리는 고정되어 있기 때문에 공간 복잡도 0(1) 

def fib_optimized(n):
    # 코드를 작성하세요. 
    # 1,1,2,3,5,8...
    current = 1 
    previous = 0 
    for i in range(1,n):
        current_copy  = current 
        current = previous + current 
        previous = current_copy 
    return current          

    
    


# 테스트
print(fib_optimized(16))
print(fib_optimized(53))
print(fib_optimized(213))

 

# 출처: https://heytech.tistory.com/65#

[알고리즘] 다이나믹 프로그래밍(DP)에 대해 알아보자! (+Python 구현)

# 출처: 코드잇