반응형
☝ 다이나믹 프로그래밍
- 동적 계획법이라고 표현하기도 함
- 다이나믹 프로그래밍으로 해결할 수 있는 대표적 예시 👉 피보나치 수열
☝ 피보나치 수열
- 피보나치 수열 👉 이전 두 항의 합을 현재의 항으로 설정하는 수열
- 피보나치 수열 구현 예시
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)
☝ 다이나믹 프로그래밍 사용 조건
- 큰 문제를 작은 문제로 나눌 수 있을 때
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때
☝ 메모이제이션 기법
- 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
- 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
- 메모이제이션은 값을 저장하는 방법 👉 캐싱이라고도 함
- 메모이제이션 구현 방법 👉 한 번 구한 값을 리스트에 저장
- 다이나믹 프로그래밍을 적용했을 때 피보나치 수열의 시간 복잡도 👉 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 |
댓글