2022-07-27 TIL

 

 

☝ 다이나믹 프로그래밍

• 동적 계획법이라고 표현하기도 함
• 다이나믹 프로그래밍으로 해결할 수 있는 대표적 예시 👉 피보나치 수열

 

 

☝ 피보나치 수열

• 피보나치 수열 👉 이전 두 항의 합을 현재의 항으로 설정하는 수열
• 피보나치 수열 구현 예시

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

print(fibo(10))

• 해당 방식은 n이 커질수록 시간이 기하급수적으로 증가 👉 O(2*n)

 

 

☝ 다이나믹 프로그래밍 사용 조건

1. 큰 문제를 작은 문제로 나눌 수 있을 때
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때

 

 

☝ 메모이제이션 기법

• 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
• 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
• 메모이제이션은 값을 저장하는 방법 👉 캐싱이라고도 함
• 메모이제이션 구현 방법 👉 한 번 구한 값을 리스트에 저장
• 다이나믹 프로그래밍을 적용했을 때 피보나치 수열의 시간 복잡도 👉 O(N)
• 피보나치 수열 메모이제이션 기법으로 구현

d = [0] * 100

def fibo(x) :
  if x == 1 or x == 2 :
    return 1
  if d[x] != 0 :
    return d[x]
  d[x] = fibo(x-1)+fibo(x-2)
  return d[x]

print(fibo(99))