1. 다이나믹 프로그래밍 (Dynamic Programming, 동적 계획법)
- 조건
ㄴ 큰 문제를 작은 문제로 나눌 수 있다.
ㄴ 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
- Top-Down 방식 : 큰 문제를 해결하기 위해 작은 문제를 호출
- Bottom-Up 방식 : 작은 문체부터 답을 도출
2. 메모이제이션 (Memoization) or 캐싱 (Caching)
한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
📌 파보나치 수열 코드 - 재귀적 + 메모이제이션 - 탑다운
#한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100
# 파보나치 함수를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x) :
#종료 조건 (1 또는 2일 때 1반환)
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))
📌 파보나치 수열 코드 - 반복적 + DP 테이블 - 보텀업
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
#피보나치 함수 반복문으로 구현 (보텀업 다이나믹 프로그래밍)
for i in range(3, n+1) :
d[i] = d[i-1] + d[i-2]
print(d[n])
3. recursion depth
재귀함수로 구현 시 recursion depth 오류 발생하는 경우, sys 라이브러리의 setrecursionlimit() 호출하여 재귀 제한 완화
'✍ Coding Test > Python' 카테고리의 다른 글
| [Coding Test] 이코테 - 최단 경로 (0) | 2023.05.24 |
|---|---|
| [Coding Test] 이코테 - 이진 탐색 (0) | 2023.05.22 |
| [Coding Test] 이코테 - 정렬 (0) | 2023.04.26 |
| [Coding Test] 이코테 - DFS/BFS (0) | 2023.04.25 |
| [Coding Test] 이코테 - Implementation (구현) (0) | 2023.04.20 |