다이나믹 프로그래밍(Dynamic Programming) - 메모제이션

다이나믹 프로그래밍이란 주어진 문제를 한 번의 수행으로 풀도록하는 알고리즘이다.

 

보편적으로 분할정복기법을 사용하는데 이 기법은 동일한 수행을 다시해야한다는 단점이있다.

이러한 대표적인 예시가 피보나치수열

피보나치 수열에서 F(15)를 구하려면 F(14)와 F(13)을 구해야한다.

F(14)를 구하려면 F(13)과 F(12)를... 이런식으로 나아간다. -> 비효율적

 

이럴 때 예를 들어 F(12)가 중복적으로 나오는 경우가 생길 것이다.

이렇게 되면 동일한 데이터를 반복적으로 불필요하게 실행하게 된다. ->단순하게 분할정복기법을 사용하면 안된다.

->이럴 때 다이나믹 프로그래밍 기법을 사용해야한다.

 

다이나믹 프로그래밍은 다음의 예시에 사용가능하다.

 

-큰 문제를 작은문제로 나눌 수 있다.

-작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 ->동일하기 떄문에 작은문제에서 구한 정답을 배열에 저장해놓은 다음에 큰 문제에서 이용할 때 이용한다.

 

즉 크고 어려운 문제가 있음녀 그것을 잘게 나누어 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것이다.

이 과정에서 메모제이션(Memozation)을 사용한다는 점이 분할정복과 다르다. 

이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야할 때 는 저장된 값을 단순히 반환하기만 하면된다.

코드를 구현하면 아래와 같이 된다.

function fibonacci(n) {
  const memo = [0, 1]; //const로 선언
  const aux = (n) => { //재귀함수 aux. memo배열을 조회하고, 값을 저장하는 역할
    
    //memo 배열 안에 해당 값이 있는지를 먼저 조회 = 최적화
    if (memo[n] !== undefined) { 
      return memo[n]; //피보나치(5)면 5번째 숫자를 return한다.
    } 
    
    //memo 배열 안에 해당 값이 없는 경우
    else {
      memo[n] = aux(n - 1) + aux(n - 2);
    }
    
    //피보나치(5)는 aux(4) + aux(3)을 조회하고 aux(4)는 다시 aux(3)과 aux(2)를 조회하고...
    //결국 memo안에 가지고 있는 요소를 찾아와서 활용하여 aux(2), aux(3) ... 을 순서대로 memo배열에 저장하는 것
    
    return memo[n]; //memo배열의 n번째 인덱스 값이 aux함수의 return 값이 되는 것
  };
  
  return aux(n);
};

 

출처

https://blog.naver.com/ndb796/221233570962

20. 다이나믹 프로그래밍(Dynamic Programming)