데이터 구조 및 분석 : Dynamic Programming

본 게시글은 Edwith 문일철 교수님의 데이터 구조 및 분석: Linear Structure and Dynamic Programming을 듣고 정리한 내용입니다.

1. Dynamic Programming 

• 중복되는 sub-instance가 있는 형태의 recurrence를 푸는 일반적인 알고리즘.
• Setting up a recurrence :
  - 큰 instance의 해답을 작은 instance들의 해답과 연결시키는 것. 
  - (1) 작은 instance를 하나 풀어본다. 
  - (2) table에 해답을 기록한다.
  - (3) table에서 larger instance의 해답을 추출한다.
  - 즉, 작은 size부터 풀면 큰 사이즈까지 다가갈 수 있다. 

2. Memoization 

• dynamic programming의 핵심은 overlapping하는 small instance들을 계산하지 않겠다는 의미. 그 해결책으로써 결과를 기록하는 방법을 선택. 
• 즉, 이전 function call을 미래에 재활용하기 위해 그 결과를 저장하는 것. 
• Bottom-up approach.

3. Fibonacci Sequence in DP 

def FibonacciDP(n):
	# setting up a memoization table
    dicFibonacci = {} 
    dicFibonacci[0] = 0
    dicFibonacci[1] = 1
    # building up a bigger solutions
    for itr in range(2, n + 1):
        dicFibonacci[itr] = dicFibonacci[itr - 1] + dicFibonacci[itr - 2]
    return dicFibonacci

# Execution part
for itr in range(0, 10):
    print(FibonacciDP(itr))

• 총 N개의 table 칸이 필요 => O(N)만큼의 space가 필요. 
• execution을 $O(2^n)$에서 $O(N)$으로 줄일 수 있게 되었다.