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

 

다이나믹 프로그래밍이란?

• 다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.
• 방식은 분할정복과 같으나 분할정복은 계산한 부분문제를 단 한번만 쓰고 더이상 사용하지않는다.
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
• 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(top-down) 방식과 보텀업(bottom-up) 방식이 있다.

---

메모이제이션(Memoization)

• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나다.
• 한 번 계산한 결과를 말 그대로 메모리 공간에 메모하는 기법이다.
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
  • 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
• 메모이제이션은 한 번 구한 정보를 리스트에 저장하는 형태로 구현할 수 있다.
  • 이 리스트를 보통 DP테이블이라고 부른다.

 

---

동작방식

1. 구하고자 하는 큰 문제를 작은 문제들로 나눈다. (점화식을 세운다.)
2. 가장 작은 부분문제를 푼 뒤 값을 저장한다. = 메모이제이션
3. 메모이제이션 된 문제들의 값을 이용해 점차 더 큰 문제들의 답을 구한다.
4. 가장 큰 문제를 풀이할때까지 반복한다.

 

☆무엇을 어떻게 저장할지 정하는게 중요하다.

---

구현 방법

 

Bottom-up 방식 (반복문 사용)

아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식

 

 

 

Top-down 방식 ( 재귀 사용)

위에서부터 함수를 호출시켜서 재귀로 문제를 해결하는 방식