JS 알고리즘 24일차 - 동적 프로그래밍

동적 프로그래밍 정의 복잡한 문제를 더 간단한 하위 문제의 모음으로 쪼개서 각 하위 문제들을 풀어서 그 답을 저장하는 방식으로 문제를 푸는 방법 언제 동적 프로그래밍을 사용하는가? 동적 프로그래밍을 사용할 수 있는지를 확인하기 위해서는 두 가지를 확인해야 한다. 최적 부분 구조가 존재하는지 여부 반복되는 하위 문제가 있는지 여부 예시 function fib(n) { if (n <= 2) return 1; return fib(n-1) + fib(n-2); } 단점 시간복잡도가 O(2^n)이라서 많이 느리다. Memo에 값을 저장하는 방법 반복되는 하위 문제에 대한 답을 저장하는 방법 예시 function fib(n, memo=[]) { if (memo[n] !== undefined) return memo[n]; if (n <= 2) return 1; let res = fib(n-1,memo) + fib(n-2, memo); memo[n] = res; return res; } 시간 복잡...

원문링크 : JS 알고리즘 24일차 - 동적 프로그래밍