목차
DP
- 문제에 대한 정답이 될 가능성이 있는 모든 해결책을 체계적이고 효율적으로 탐색하는 풀이
- Top-down / Bottom-up 방식이 존재
- 최대/최소, 방법의 개수 등을 구할 때 주로 사용
- 미래의 계산이 앞선 계산 결과에 영향을 받을 때 주로 사용
DP 문제해결 과정
- 크고 복잡한 문제를 작은 문제들로 나눔 : subproblem(하위문제)
- 하위 문제의 답을 계산
중복 계산해야 하는 하위 문제가 존재 : overlapping subproblem(중복하위문제)
한 번 계산한 결과는 메모리에 저장하여 재계산하지 않도록 함 => 속도 향상(memoization, dp table) - 하위 문제에 대한 답을 통해, 원래 문제에 대한 답을 계산 : potimal substructure(최적 부분 구조)
* 최적 부분 구조: 하위 부분 문제에서 구한 최적의 답이, 합쳐진 큰 문제의 최적의 답을 구할 수 있는 구조
피보나치 수열
- f(n) = f(n-2) + f(n-1)
- 완전탐색(재귀)으로 해결 시, 시간복잡도 O(2^n)
- DP로 해결 시, 시간 복잡도 O(n)
- 반복되는 계산 부분, memoization
memo = {}
def fibo(n):
#초기값
if n==1 or n==2:
return 1
#dp 테이블에 없으면 직접 계산하여 추가
if n not in memo:
memo[n] = fibo(n-1) + fibo(n-2)
return memo[n]
Top-down vs Bottom-up
-
Top-down(memoization) Bottom-up(tabulation) 재귀 사용 => 구현 시간이 빠름 반복문 사용 => 실행 시간이 빠름 재귀풀이에서 중복되는 계산 값을 저장.
이후 동일한 함수 호출시 재활용더 작은 subproblem에 대한 계산 결과를
DP table에 저장하여 큰 문제 계산에 활용hash talbe 또는 list에 계산 결과를 저장 - 재귀함수로 비효율적인 완전 탐색 코드 작성 -> 중복되는 subproblem에 계산 결과를 저장 -> 이후 바텀업으로의 전환 고려
참고자료