본문 바로가기
내가 공부하려고 올리는/TIL

2022-07-27 TIL

by 결딴력 2022. 7. 27.
반응형

 

 

☝ 다이나믹 프로그래밍

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

 

 

 피보나치 수열

  • 피보나치 수열 👉 이전 두 항의 합을 현재의 항으로 설정하는 수열
  • 피보나치 수열 구현 예시
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))

 

 

반응형

'내가 공부하려고 올리는 > TIL' 카테고리의 다른 글

2022-08-01 TIL  (0) 2022.08.01
2022-07-29 TIL  (0) 2022.07.30
2022-07-26 TIL  (0) 2022.07.27
2022-07-22 TIL  (0) 2022.07.22
2022-07-21 TIL  (0) 2022.07.21

댓글