[알고리즘] 다이나믹 프로그래밍

[알고리즘] 다이나믹 프로그래밍

---

큰 문제를 작은 문제로 나눠서 푸는 알고리즘

1. Overlapping Subproblem

   겹치는 부분 문제

2. Optimal Substructure

   문제의 정답을 작은 문제의 정답에서 구할 수 있을 때

Overlapping Subproblem

큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.

문제를 작은 문제로 쪼갤 수 있다.

ex. 피보나치 수

Optimal Substructure

문제의 정답을 작은 문제의 정답에서 구할 수 있다.

ex.

서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면

대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다.

이 두 가지를 활용하는 것이 다이나믹 프로그래밍!

• 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 함

• Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같음

• 따라서, 정답을 한 번 구했으면, 정답을 어딘가에 메모해놓기

• 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있음

• 메모를 한다고 해서 영어로 Memoization이라고 부름

푸는 접근 방법

• Top-down

  문제를 작은 문제로 나눈다.

  작은 문제를 푼다.

  작은 문제를 풀었으니, 원래 문제를 푼다.

  재귀 호출 이용

• Bottom-up

  문제를 크기가 작은 문제부터 차례대로 푼다.

  문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.

  작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.

  그러다보면, 원래 문제를 풀 수 있게 된다.

  보통 for문을 이용

문제 풀이 전략

• Top-down

  dp[i]를 생성하여 i번째에 해당하는 값을 구하는 식을 만든다. i-1과 i-2 이용

• Bottom-up

  for문을 사용해서 i가 가장 작을 때부터 n까지 dp[i]에 값을 저장시킨다.