[파이썬] '다이나믹 프로그래밍' 개념 및 예제

다이나믹 프로그래밍 => 한번 계산한 문제는 다시 계산 X !! (중복 줄이기)

언제 사용?

1. 큰 문제를 작은 문제로 나눌 수 있을 때
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일

다이나믹 프로그래밍과 분할 정복과의 차이점: 분할은 하지만, 서로 영향을 끼친다 (중복이 있음)

 

 

ex)

피보나치 수열을 재귀적으로 처리하면 n이 커질수록 수행 시간 너무 커짐.

# (재귀) 피보나치
def fibo(X):
	if x==1 or x==2:
		return 1
	return fibo(x-1)+fibo(x-2)

 

 

-> 탑다운 (큰 문제 해결을 위해 작은 문제 부름)

한번 구한 결과는 저장해두었다가 그대로 불러오자 ( 메모이제이션 기법 => 캐싱 )

#(재귀-메모이제이션) 피보나치

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]
    

 

 

-> ★보텀업 ( 작은 문제부터 답 도출 _ 단순 반복문)

# (반복_보텀업) 피보나치

d=[0]*100 # 먼저 계산된 결과 저장할 dp 테이블

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])

 

다이나믹프로그래밍의 전형적인 형태 : 보텀업(하향식)

-> 결과 저장용 리스트 : DP 테이블 ( 메모이제이션은 탑다운에 국한하여 씀)

 

 

'이것이 취업을 위한 코딩테스트다 python -나동빈' 책과 유튜브 강의를 보고 공부한 내용입니다.