Dynamic Programming (DP)

netflix

 

 

땅따먹기 문제를 풀고 있는데 2시간동안 생각을 하는데 도저히 안 풀렸다.  계속 시간초과가 나서 이것저것 시도 해보다가   힌트라도 보자해서 봤던게 바로 DP였습니다.

 

그럼 DP는 과연 무엇일까?

 

Dynamic Programming  (동적 계획법) 

DP 뭔가 어려워보이는데 그냥 "기억하면서 문제 풀기"라고 생각하면 편합니다.  

이게 뭔말이지 싶겠지만 5분만 참고 글을 읽으면 바로 이해 가능합니다. 

 

예제는 직접 눈으로 보고 느끼면 이해가 더 쉽기에 간단한 예제를 가져와봤습니다. 

바로 `피보나치 수열`입니다.

https://m.blog.naver.com/tipsware/221276742221

피보나치 수열 : 앞 두 개의 항목의 합이 그 다음 항목의 값이 되는 수열을 의미한다. 

 

const fib = (n) => {
  if (n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
};

console.log(fib(7));

// console.log(fib(45));

지금 바로 이 코드를 가져가서 실행을 시켜보세요!

0.11  seconds 정도 걸립니다.  

 

fib(7)을 실행하면 24개의 함수가 호출이됩니다.  그렇다면 n이 늘어나면 훨씬 더 많은 함수가 호출되지 않을까요 ? 그럼 시간이 더 오래걸리지 않을까요?

 

그럼 `fib(45)`는 과연 얼마나 걸릴까요 ?   이것도 직접 해보세요

저는 일단 6.427 seconds 정도 걸립니다.  

 

fib(50)? 은 어떨까요

엄~~~~~~청 오래 걸립니다. 

시간 복잡도가 O(2^n) 이기 때문에 약 1,125,899,906,842,624 단계를 거쳐야 정답이 나옵니다.  즉 약 1000조 단계를 거쳐야 한다는 겁니다. 

 

쉽게 말해 n이 커질수록 재귀 호출의 수가 많아져서 시간이 엄~~~~청 오래걸린다는 소리입니다.

 

그럼 어떻게해야 이 시간을 단축할 수 있을까요? 

지금 잘 보시면 fib(7) 함수를 실행하면 중복되는 트리가 많이 나옵니다.  

 

먼저 fib(4) 함수만 결과가 똑같은데 3번이 호출되었고,  fib(5) 함수도 결과가 같은데 두 번이나 호출이되었습니다. 

그렇다면 n이 더 커진다면 이렇게 중복적인 호출이 더 많아질 수 있겠죠?  

이렇게 반복해서 호출되는 함수는 처음 호출될 때 return 값을 저장해서 다시 그 함수가 호출되면 저장된 값을 가져온다면  불필요한 호출을 막을 수 있지 않을까요 ? 

 

이걸 DP에서는 Memoization 이라고 하는데 그냥 '반복 되는 작업의 결과값을 메모하는 구나'라고 생각하시면 됩니다.

  

메모하는 방법은 여러가지겠지만 그중 한 가지로 위 문제를 해결해보겠습니다. 

const fib = (n, memo = {}) => {
  if (n in memo) return memo[n];
  if (n <= 2) return 1;
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
};

console.log(fib(100));

이 코드를 가지가서 바로 실행해보시면 확실히 개선된것을 느끼실 수 있습니다. 

 

아까 `fib(50)` 이 한참 기달려도 결과값이 안나왔는데 `fib(100)`을 `0.113 seconds` 만에 처리해버립니다. 

 

예를들어 `fib(6)`를 실행 하면 아래처럼 한 번 호출된 함수의 결과값은 전부 메모가되어서 재호출되면 이전처럼 맨 마지막까지 호출되지 않습니다. 

 

 

 

 

재호출 할때는 key 값으로 바로 가져오니 엄청나게 시간이 단축이 됩니다.  

그래서 결과적으로 시간 복잡도는 2n  즉 `O(n)`이 됩니다.  

 

 

 

그럼 DP는 언제사용하는게 좋을까?

1) DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제

2) 중복 계산이 많이 발생하는 문제  

3) 작은 부분 문제로 분할할 수 있는 문제: 큰 문제를 작은 부분으로 분할할 수 있으며, 작은 문제의 최적해가 전체 문제의 최적해에 영향을 미칠 때 동적 계획법은 유용합니다.

4) 위 조건을 충족하면서 정확한 결과가 필요할 때 : DP는 작은 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구하는 방식으로 작동하기 때문에 정확한 결과를 제공합니다. 

 

 

DP의 단점

1. 메모리 사용량: DP는 중간 결과를 저장해야 하므로 메모리 사용량이 크게 증가할 수 있습니다. 

2. 순환식 세우기의 어려움: DP를 적용하기 위해서는 문제를 순환식으로 표현해야 합니다. 순환식을 세우는 과정은 문제에 따라 어려울 수 있으며, 잘못된 순환식을 세울 경우 잘못된 결과를 얻을 수 있습니다. 

 

 

 

DP와 다른 알고리즘의 차이점

 

1. 그리디 알고리즘:  DP와 달리 지금의 선택만을 고려하므로 계산 시간이 짧고 메모리 사용량이 작을 수 있습니다. 그러나 그리디 알고리즘은 항상 최적해를 보장하지는 않으며 최적해에 도달하지 못할 수도 있습니다. 

 

2. 분할 정복 : 분할 정복은 문제를 작은 부분 문제로 분할하고 각각을 독립적으로 해결한 후, 이를 결합하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. DP와 마찬가지로 문제를 작은 부분 문제로 분할하여 해결하지만, 중복 계산을 피하는 방식이 아니기 때문에 DP보다는 계산 시간이 증가할 수 있습니다. 

 

 

연습 문제

문제 링크

프로그래머스

 

풀이 설명

[프로그래머스 - JS,PYTHON] level.3 정수 삼각형

---

Reference

Demystifying Dynamic Programming

Dynamic Programming

Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges