DP란
- dp는 메모리를 사용해 수행 시간 효율을 향상 시키는 방법.
- 이전의 계산 값을 저장해 다시 계산하지 않도록 한다.
- 탑다운, 보텀업 방법으로 나뉜다.
DP 문제의 조건
- 최적 부분 구조
- 큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 값을 모아 큰 문제의 값을 도출 가능할 때
- 중복 부분 문제
- 동일한 작은 문제를 반복적으로 해결할 때.
DP 접근법
- 그리디 , 구현, 완전 탐색 등 알고리즘으로 할 수 있을지 검토.
- 작은 문제를 조합해 해결할 수 있을 때, 즉 부분 문제 중복인 경우 DP 사용.
- 일반적으로 dfs/bfs로 완전 탐색 작성 뒤 작은 문제에서 구한 답이 또 쓰일 때 코드를 개선하는 방법으로 사용.
DP 해결 방법
- 탑다운의 경우 메모이제이션을 사용하는게 일반적이고 보텀업 방식은 DP테이블을 만들어 해결.
- 점화식 을 통해 해결하는 방법이 많아 점화식 도출 중요.
탑다운 피보나치
dp = [0]*100
def fibo(x):
if x == 1 or x == 2 :
return 1
if dp[x] != 0:
return dp[x]
dp[x] = fibo(x-1) + fibo(x-2)
return dp[x]
print(fibo(99))
보텀업 피보나치
dp = [0] * 100
dp[1] = 1
dp[2] = 1
for i in range (3, 100):
dp[i] = dp[i-1] + dp[i-2]
print(dp[99])DP vs 분할 정복
- 모두 최적 부분 구조를 가질 때 사용할 수 있음.
- 부분 문제의 중복의 차이점.
- dp의 경우 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨.
- 분할 정복의 경우 동일한 부분 문제가 반복적으로 계산 안됨.
DP 문제 예시
호기심많은 개발자