하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용. 기억하며 풀기
- 사용하는 이유: 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 가능-> 앞에서 계산된 값을 다시 반복할 필요 X -> 효율적임
- 예시: 피보니치 수열
- F(n)=F(n-1)+F(n-2)를 재귀 호출 2번 하여 계산했을 때 수가 커지면 호출함수의 횟수가 기하급수적으로 늘어나 비효율적임
- 또한 F(n-1)에서 구한 값을 F(n-2)에서 또 구하게 되므로 비효율적
- 만약 DP를 사용하여 한번 구한 작은 문제의 결과값을 저장해두고 재사용이 가능 -> 효율적
- O(n^2)를 O(f(n))으로 개선 가능
- 예시: 피보니치 수열
- Overlapping Subproblems(겹치는 부분 문제)
- DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구함 -> 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능
- 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다
- 예시: 피보나치 수열
- 위와 같이 f(3), f(2), f(1)과 같이 동일한 부분 문제가 중복되어 나타남 -> 저장된 값 재활용이 가능
- Optimal Substructure(최적 부분 구조)
- 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우
- 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일
- 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용 가능
- 피보나치 수열도 동일하게 이전의 계산 값을 그대로 사용하여 전체 답을 구할 수 있어 최적 부분 구조임
- DP로 풀 수 있는 문제인지 파악
- 제일 어려움
- 문제가 작은 문제들로 이루어진 함수로 표현 가능한지 파악해
- 사용 조건 2가지가 맞는지 판단
- ex. 특정 데이터 내 데이터 최소화/최대화 계산, 특정 조건 내 데이터 세기, 확률 등의 계산
- 문제의 변수 파악
- 점화식 (변수 간 관계식) 만들기
- 예를 들어 f(n)=f(n-1)+f(n-2) 같은 식
- 메모하기(Memoization or tabulation)
- 변수의 값을 저장하는 것 -> 메모한다
- 기저 상태 파악
- 가장 작은 문제의 상태를 아는 것
- 예를 들어 f(0) = 0, f(1) = 1
- 구현
- Bottom-Up (Tabulation 방식) - 반복문 사용
- Top-Down (Memoization 방식) - 재귀 사용