Dynamic Programming 동적 프로그래밍

📌  동적 프로그래밍이란 ?

 

동적 프로그래밍이라고 해서 동적으로 ?!? 프로그래밍이 이루어지는 건 아니다 ㅋㅋㅋ

큰 문제를 작은 문제로 나누어 푸는 법을 말한다.  ->  그럼 분할 정복 아닌가 ?

 

📍  Divide and Conquer 분할 정복이란 ?

분할 정복도 큰 문제를 작은 문제로 나누어 푸는 법이다.
그러나 동적 프로그래밍과는 큰 차이점이 있다.
분할 정복은, " 작은 문제 " 에서 반복이 일어나지 않는다.
동적 프로그래밍은, " 작은 문제 " 에서 반복이 일어난다.  ->  불필요한 일들이 반복적으로 일어난다.

 

즉, 분할 정복은 진짜 큰 문제를 여러 개로 작게 작게 나눠서 푸는 방식이라면,

동적 프로그래밍은 어짜피 반복되는 작은 문제들을 한 곳에 묶어 놓거나(?) 기록(?) 하는 식으로 

불필요한 반복들을 줄이면서 큰 문제를 해결하는 방식을 말한다.

 

📍  Memoization 메모이제이션이란 ?

동적 프로그래밍에서 반복되는 작은 문제들을 " 기록 " 을 통해 불필요한 반복을 해결하는 방식이다.
한 번 계산한 작은 문제의 값은 재사용하기 한 곳에 저장(기록) 해놓는다.

 

// memoization 예시

function memoization_fib(n){
  let memo = [];
  
  memo[0] = 0;
  memo[1] = 1;
  
  if(n <= 1) return memo[n];
  
  for(let i=2; i<n; i++){
  	memo[n] = memo[n-1] + memo[n-2]
  }
  
  return memo[n];
}

// f(2) = f(1) + f(0)
// f(3) = f(2) + f(1) = f(1) + f(0) + f(1)
// f(4) = f(3) + f(2) = f(2) + f(1) + f(1) + f(0) = f(1) + f(0) + f(1) + f(1) + f(0)

// -> 작은 문제들이 반복된다.
// -> 같은 문제는 구할 때마다 정답이 같다.

// 반복되는 값들을 배열에 저장해두고 필요할 때마다 꺼내 쓴다. ^__^

 

 

📌  구현 방법 : Bottom-up & Top-down

 

◾  Bottom-up

 

// Bottom-up 
// 아래부터 차근차근, 값을 구해 나가는 방식이다. 아래 -> 위

// 대부분의 반복문이 Bottom-up 방식에 해당된다.

function fibo_bottom_up(n){
  if(n <= 1) return n;
  
  let front = 0;
  let next  = 1;
  
  for(let i=1; i<n; i++){
  	
    let sum = front + next;
    front = next;
    next = sum;
    
  }
  
  return sum;
}

// fibo_bottom_up(6)을 구한다고 가정했을 때,

// i=1, sum=1, front=1, next=1
// i=2, sum=2, front=1, next=2
// i=3, sum=3, front=2, next=3
// i=4, sum=5, front=3, next=5
// i=5, sum=8, front=5, next=8     return되는 값은 8이다.

// 아래부터 차례대로 차근차근 올라오는 과정을 확인할 수 있다.

 

 

◾  Top-down

 

// Top-down
// 큰 문제를 풀 때 작은 문제를 풀어야 값이 나온다는 걸 알아야 ㅋㅋ 그제서야 작은 문제를 해결하는 방식이다.
// 차근차근 방식 절대 아님 X 필요한 작은 문제들만 해결하고 답을 도출 ! 위 -> 아래

// 대부분의 재귀 함수가 Top-down 방식에 해당된다
// fibo_top_down(6)을 구하기 위해 fibo_top_down(5)와 fibo_top_down(4)를 구하기 시작함

function fibo_top_down_recur(n){
  if(n <= 1) return n;
  return fibo_top_down_recur(n-1) + fibo_top_down_recur(n-2);
}


// 우리는 Dynamic Programming 을 배우고 있으니,
// 이미 구한 값을 또 구하는 낭비는 하지 않도록 코드를 짜자 !~ :)

function fibo_top_down_dp(n){
  let memo = [0, 1];
  
  if(n <= 1) return memo[n];
  
  for(let i=2; i<n; i++){
  	memo[n] = memo[n-1] + memo[n-2]
  }
  
  return memo[n];
}

 

 

📌  동적 프로그래밍을 활용한 문제 풀이 예시

 

2021.10.12 - [개발 공부/Algorithm] - 자바스크립트 프로그래머스 거스름돈 문제 풀이

자바스크립트 프로그래머스 거스름돈 문제 풀이