[알고리즘]DP(Dynamic Programming) 내가 이해한 정리

• 알고리즘 유형 : DP
• DP에 대한 개념 정리와 내용은 하기 링크에 매우 자세하고 친절히 되어 있습니다. 
• 참고 : https://antaehyeon.github.io/devlog/2018/05/08/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EC%86%8C%EA%B0%9C/
• 참고 : https://hongjw1938.tistory.com/47

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다.

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사드리겠습니다. 

---

정의

- 큰 문제를 작은 문제로 쪼개서 그 답을 저장해 두고 재활용한다.

---

사용 이유

- 재귀와 유사하지만 재귀를 단순하게 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다.
- DP 사용 시 시간 복잡도 : O(n^2) → O(f(n)) 로 개선(몇몇 케이스)

 

---

DP의 사용 조건

1) Overlapping Subproblems(겹치는 부분 구조)
      - 문제를 작은 부분 문제로 나눠서 풀 수 있다. 
      - 반복되는 작은 문제를 재활용
      - 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
      - 문제를 작은 문제로 쪼갤 수 있다.
2) Optimal Substructure(최적의 부분 구조)
      - 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
      - Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

---

DP 사용하기

- DP는 방법론이므로 다양한 활용 범위를 갖고 있다. 
   1) DP로 풀 수 있는지 확인
      - DP 사용 조건 확인
      - 예) 특정 데이터 내 최대/최소화, 특정 조건 데이터 카운팅, 확률 등
   2) 문제의 변수 파악
    - 변수에 따라 그 결괏값을 재사용해야 한다. 
      - 따라서 문제 내 변수의 개수를 알아야 하며 이것을 state를 결정한다라고 한다.
   3) 변수 간 관계식 만들기(점화식)
     - 반복되는 변수의 결괏값을 이용하기 때문에 점화식을 세울 수 있다.
   4) 메모하기
   - 변수의 값에 따른 결과를 저장한다. >>> 메모(Memoization)
      - 변숫값에 따른 결과를 저장(메모)하여 그 저장된 값을 재활용하는 것
   5) 기저 상태 파악하기
     - 가장 작은 문제의 상태를 알아야 한다. 
      - 피보나치수열에서는 f(0) = 0, f(1) = 1과 같은 방식
   6) 구현하기
      - Bottom-Up (Tabulation 방식)-반복문
      - Top-Down (Memoization 방식)-재귀

---

DP 구현 방법

1) Bottom-Up
    - dp [0]이 기저 상태, dp [n]이 목표일 때 n까지 값을 전이시켜 재활용하는 방식

2) Top-Down
     - dp [0]의 기저 상태에서 출발 하나, dp [n]을 찾기 위해 위부터 호출하여 dp [0]까지 내려간 후 결괏값을 재귀를 통해 전이시켜 재활용하는 방식

---

분할 정복과의 차이점은?

1) 같은 점
  - 주어진 문제를 작게 쪼개서 하위 문제로 해결하고, 연계적으로 큰 문제를 해결한다는 동일
2) 차이점
  - 분할 정복 : 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우 사용
         예) 병합 정렬
  - DP : 동일한 중복이 일어나면 사용
         예) 피보나치수열