[CodingTest]Dynamic Programming(DP, 동적 계획법)

Dynamic Programming(DP, 동적 계획법)

모든 경우의 수를 조합해 최적의 해법 찾기

문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결

하나의 문제는 단 한 번만 풀도록 하는 알고리즘

조건

• Overlapping Sub-problems(부분 반복 문제) - 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제가 중복해서 발견
• Optimal Substructure(최적 부분구조) - 작은 문제에서 구한 정답은 큰 문제에서도 사용 가능

---

Overlapping Sub-problems

---

피보나치 수열

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

fib(5) 는 두 번, fib(4) 는 세 번, fib(3) 은 다섯 번의 동일한 계산을 반복

주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 함

---

Optimal Substructure

---

정답은 최적의 해결 방법(Optimal solution)을 의미

작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 함

결국 전체 문제의 최적의 해법(Optimal solution) 구할 수 있음

A에서 D로 가는 최단 경로는 작은 문제인 A에서 C로 가는 최단 경로, 그리고 한 번 더 작은 문제인 A에서 B로 가는 최단 경로의 파악 가능