[algorithm]dp

less than 1 minute read

Dynamic Programming

큰 문제를 작은문제로 나누어 푸는 알고리즘

(동적계획법이란 이름은 그냥 멋있어서 부여했다고..?)


1.1

divide and conquer와 유사하지만 차이점은 작은 문제가 중복이 일어나는지 안일어나는지 확인.
분할 정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누는 방법.
동적프로그래밍은 작은 부분문제들이 반복되는것(답이 변하지 않는것)을 이용해 풀어나가는 방법.

1.2

모든 작은 문제들은 한번만 푼다. 따라서 정답을 구한 작은 문제를 기억하고 큰 문제를 풀어갈 때 작은문제가 반복되면 기억한 것을 이용해 결과를 만든다.

1.3

조건

  • 작은 문제가 반복이 일어나는 경우
  • 같은 문제는 구할 때마다 같은 정답이 결과로 나오는 경우

1.4

Memoization
동적프로그래밍 ex_ 피보나치


2. Bottom-up vs Top-down방식

2.1 구현방법

1. Bottom-up


작은 문제부터 차근차근 구해나가는 방법

2. Top-down


재귀함수로 구현하는 경우
큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그때 작은문제를 해결한다.


요약

  • 1.DP는 큰 문제를 작은 문제들로 분할하여 그것을 이용해 큰 문제를 해결하는 방법
  • 2.분할정복과 다른점은 DP의 경우 작은 부분 문제의 답이 항상 같아야 한다는 것.

참고

Updated: