다이나믹 프로그래밍 개념 정리

• 조건
  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
• 메모이제이션(Memoization)
  • 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
  • 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져옴
  • 캐싱이라고도 함.
  • 한 번 구한 정도를 리스트에 저장하는 방식으로 사용 → 사전 자료형 사용할 수 있음.
• 탑다운(하향식): 재귀 함수를 이용, 큰 문제 해결하기 위해 작은 문제 호출
  • 피보나치 수열

#한번 계산된 결과 메모이제이션 하기 위한 리스트 초기화
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))

• 보텀업(상향식): 반복문을 이용, 작은 문제부터 차근차근 답을 도출
  • 피보나치 수열 

#앞서 계산된 결과 저장위한 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])

• 문제 푸는 단계
  1. 다이나믹 프로그래밍 유형임을 파악: 특정 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리는 경우 DP를 적용할 수 있는지, 해결하고자 하는 부분 문제들의 중복 여부 확인
  2. 일단 단순히 재귀 함수로 비효율적인 프로그램 작성 하고(탑다운) 작은 문제에서 구한 답 큰 문제에서 그대로 사용될 수 있으면 코드 개선
  3. 가능하다면 재귀 쓰는 탑다운보다 보텀업 방식으로 구현: 재귀 함수의 스택 크기 한정되어 있을 수 있음. → setrecursionlimit() 함수 호출해서 재귀 제한 완화 가능

 

*해당 내용은 "이것은 취업을 위한 코딩테스트다 with python"을 정리한 내용입니다.