# DP

• 필요한 계산 값을 저장해 두었다가 재사용 하는 알고리즘 설계 기법
  

• 다음과 같은 조건을 만족할때 사용 가능
  1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다. 이러한 작은 문제의 답을 모아 큰 문제를 해결 가능

  2. 중복된 하위 문제 : 동일한 작은 문제를 반복적으로 해결해야 함

피보나치 수열

• DP의 대표적인 예시
• 피보나치 함수를 재귀함수 이용해 구현한 코드

def fibo(x):
	if x == 1 or x == 2:
    	return 1
    return fibo(x-1) + fibo(x-2)

• 위의 코드의 시간복잡도는 O(2^N)으로써, 조금만 N이 증가해도 수행시간이 기하급수적으로 늘어남
  
• 동일한 함수가 반복적으로 호출(fibo(1), fibo(2) 등)을 볼수 있는데 이러한 반복적인 계산을 방지해주기 위한 설계 기법

Topdown

• 메모이제이션 사용해 구현하는 방법
• 메모이제이션이란 한번 구한 계산 결과를 메모해두고, 같은 식을 다시 호출하면 그 결과를 그대로 가져와서 사용
• 큰 문제를 해결하기 위해 작은 문제를 호출한다 해서 하향식으로 불림
• 재귀함수 이용해 구현

# 한번 게산된 결과를 메모이제이션하기 위한 리스트
memo = [0]*100

# 피보나치 수열을 재귀함수로 구현(topdown)
def fibo(x):
  # fibo(1)=fibo(2)=0
  if x==1 or x==2:
    return 1

  # 이미 계산한 적있는 문제라면 그대로 반환
  if memo[x] != 0:
    return memo[x]

  # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
  memo[x] = fibo(x-1)+fibo(x-2)
  return memo[x]

BottomUp

• 타블레이션(tabulation)을 사용해 구현하는 방법
• 하위 문제로부터 천천히 해결해가며 더 큰 문제를 해결하는 기법
• 상향식, DP의 전형적인 형태
• 반복문 이용하여 구현

# 작은 문제부터 해결해서 저장할 dp테이블
dp = [0]*100

# fibo(1)=fibo(2)=0
dp[1]=1
dp[2]=1
n=99

# 피보나치 수열을 반복문으로 구현(bottom up)
for i in range(3, n+1):
  dp[i] = dp[i-1]+dp[i-2]

print(dp[n])