[TIL][Thu] 동적 계획법 Dynamic Programing

조건

1. 문제가 더 작은 문제로 쪼개질 수 있을 때
2. 더 작은 문제의 solution으로 더 큰 문제의 solution을 구할 수 있을 때 : 최적 부분 구조 Optional substructure
3. subproblem들이 겹칠 때 → memoization으로 줄일 수 있음. :중복되는 부분 문제 Overlapping subproblem

접근방법 approach/Technique

• top -down
• bottom - up

	하향식	상향식
표현1	top-down	bottom-up
표현2	memoization	tobulation
가능한 에러	recur depth error
구현방식	recursion	loop
특징1	직관적	비직관적
빠르기	비교적 느림	빠름
속도차이 이유	함수 호출이 많음	불필요한 함수 호출이 x
memory 관점		높은 cache hit rate

# fibonacci

#common 
arr=[0,1]
# top-down
def fibo_recur(n):
	if n<2: return arr[n]
	else:
		fibo=fibo_recur(n-2)+fibo_recur(n-1)
		arr.append(fibo)
		return fibo

# bottom- up
def fibo_loop(n):
	if n<2: return arr[n]
	else:
		fibo=fibo(n-2)+fibo(n-1)
		arr.append(fibo)

	return arr[n]

 

with 분할정복

공통점

• 문제 분해 : 둘 다 복잡한 문제를 더 쉽고 간단한 하위 문제로 분해한다.
• 재귀 속성: 두 기법 모두 하위문제 푸는 데에 재귀를 자주 사용함.

차이점

• Dynamic P : 하위문제간 연관성 있어야 함, 중복되는 부분 문제가 존재.
• 분할정복: 하위문제간 연관성 없이 독립성 유지해도 할 수 있음.