다이나믹 프로그래밍

연산속도와 메모리공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야한다.

보텀업, 탑다운으로 나뉜다.

DP의 예시:

피보나치 수열

점화식:

인접 삼항간 점화식.

function fibonacci(x){
	if(x==1 or x==2)
		return 1
	return fibonacci(x-1) + fibo(x-2)
}

그러나, 이렇게 작성하면 O(2^n)의 지수시간 소요. N=30이면 약 10억 가량의 연산 수행.

이를 DP로 해결해보자.

DP 로 해결할 수 있는 문제의 조건

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

피보나치 수열은 이러한 문제를 만족한다.

메모이제이션(Memoization)기법을 사용하여 해결할 수 있다. 한번 구현한 결과를 메모리공간에 메모해 두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법. Caching이라고도 한다.

let d = [0] * 100

function fibo(x){
	if(x==1 or x==2)
		return 1
	if d[x] != 0 
		return d[x]
	d[x] = fibo(x-1) + fibo(x-1)
	return d[x]
}

즉 DP란,

큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

분할정복과 다른점은 문제들이 서로 영향을 미치고 있다는 점

재귀함수를 이용하면 오버헤드가 발생하므로, 반복문을 사용하면 오버헤드를 줄일 수 있다.

DP일 때의 시간복잡도는 O(N)이다.

이처럼 재귀함수를 이용하여 다이나믹 프로그래밍을 하는 방법을 , 큰 문제를 해결하기 위해 작은문제를 호출한다고 하여 탑다운 방식이라한다. 메모이제이션이 이에 해당한다.

반면 단순히 반복문을 이용하여 작성하는 경우, 보텀업방식이라고 한다.

let d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for (i = 3; i< n+1 ; i++ ){
	d[i] = d[i-1] + d[i-2]
}

console.log(d[n])

또한 메모이제이션을 Object자료형을 사용할수도 있다.

예를들어 수열처럼 연속적이지 않은 경우 유용하다.

보텀업, 탑다운으로 나뉜다.