[Coding Test] 이코테 - 다이나믹 프로그래밍

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() 호출하여 재귀 제한 완화