[TIL] 106. 동적 프로그래밍(DP)

키워드

• 동적 계획법(Dynamic Programming)
• 메모이제이션/타뷸레이션

동적 계획법(Dynamic Programming)

• 하나의 문제를 여러개로 작은 문제로 나누고(분할 정복) 중간의 작은 문제 해법을 재사용하여 큰 문제를 효과적으로 푸는 방법
  (문제의 일부분을 풀고 그 결과를 재활용하는 방법)
• 동적 계획법을 사용하기 위한 조건

1) 문제가 더 작은 문제로 쪼개질 때
2) 작은 문제의 솔루션으로 더 큰 문제의 솔루션을 구할 수 있을 때
3) 이 작은 문제에 대한 해법을 저장하고 다시 사용하여 계산의 수를 많이 줄일 수 있을 때

• 사용하게 되는 상황 : 이진 검색, 최단경로 알고리즘, 최적화 문제
  외판원 문제(링크)

• 단순 분할정복 : 분할된 서브문제(작은 문제)가 독립적 -> 즉, 그 결과를 재사용하지 않음
  DP : 분할된 서브문제의 결과를 다시 사용 -> 처리 속도가 더 빠름

[DP] 메모이제이션(Memoization ; Topdown, 하향식)

• 한번 계산했던 결과를 메모리에 저장해서 다시 사용
• 큰 문제에서 하위 문제로 접근해서 하위 문제에 대한 정답을 계산했는지 안했는지 메모리에서 확인하면서 문제를 푸는 방식
• 답을 재활용하기때문에 중복 계산을 방지

피보나치 수열 예시

def memo_fib(input_value, save_memo={}): 

    if input_value <= 0:
        return 0
    elif input_value <= 1:
        return 1
    elif input_value in save_memo:
        return save_memo[input_value]
    else:
        save_memo[input_value] = memo_fib(input_value-1, save_memo) + memo_fib(input_value-2, save_memo)
        return save_memo[input_value]

[DP] 타뷸레이션(Tabulation ; Bottomup, 상향식)

• 하위 문제의 정답을 이용해 더 큰 문제의 정답을 풀어나가는 방법
• 아래에서부터 계산을 수행하고 누적시키면서 점차 전체 큰 문제를 해결하는 방식

피보나치 수열 예시

def tabul_fib(input_value):

    f = [0, 1]

    if input_value <= 1:
        return f[input_value]

    for i in range(2, input_value+1):
        f.append(f[i-1] + f[i-2])

    return f[input_value]