동적 계획법 다이나믹 프로그래밍

Memoization으로 중복 연산을 방지하며, 작은 부분 문제로 큰 문제를 해결 하며 해를 도출하는 알고리즘 설계 기법.
수행 시간 효율성을 비약적으로 향상시키는 방법이다.

 

동적 계획법 특징

• 부분 문제는 중복되며, 상뮈 문제 해결 시 재사용한다.
• Memoization 기법을 사용한다( 동일한 계산을 반복할 때, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 따라서 이전에 계산한 값을 메모리에 저장하여 중복 연산 방지함)

 

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다.

• 1. 최적 부분 구조(Optimal Substructure)
  • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
• 2. 중복되는 부분 문제 (Overlapping Subproblem)
  • 동일한 작은 문제를 반복적으로 해결해야 한다.

 

다이나믹 프로그래밍을 이용해서 해결할 수 있는 대표 문제 
<피보나치 수열>

피보나치 수열 다음과 같은 형타의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.

1,1,2,3,5,8,13,21,34,55,89, ....

점화식이란 인접한 항들 사이의 관계식을 의미한다.

f(n) = f(n-1) + f(n-2) 

 

동적 계획법 구현 방식

• Top-down: 재귀를 통해 큰 문제를 작은 문제로 나눠 해결하며 해를 찾는 방법

//top down

function fibo_td(n, d=[]){
	if (n<2) return n;
    if(d[n] return d[n];
    
    d[n] = fibo_td(n-1) + fibo_td(n-2);
    
    return d[n];
    
 }
 
 console.log(fibo_td(5));
 console.log(fibo_td(6));
 console.log(fibo_td(7));

 

• Bottom-up: 반복문을 통해 작은 문제부터 차례대로 해를 찾는 방법

//bottom up

function fibo_bu(n, d = []){

	d[0] = 0;
    d[1] = 1;
    
    for(let i = 2; i <= n; i++){
    	d[i] = d[i - 1] + d[i - 2];
    }
    return d[n];
 }
 console.log(fibo_bu(5));
 console.log(fibo_bu(6));
 console.log(fibo_bu(7));

 

 

 

 

 

 

참고자료

1. https://www.youtube.com/watch?v=5Lu34WIx2Us&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 

2. 제로베이스