[코딩테스트 Python3 (7)] DP 동적계획법

동적계획법

문제에 대한 정답이 될 가능성이 있는 모든 해결책을 "체계적"이고 "효율적"으로 탐색하는 풀이법

1. 크고 복잡한 문제를 작은 문제들로 나눈다.
2. 하위 문제의 답을 계산한다.
   • 중복 계산해야 하는 하위 문제가 있다. [Overlapping Subproblem]
   • 한 번 계산한 결과는 메모리에 저장하여 재계산하지 않도록 한다. → 재사용
3. 하위 문제에 대한 답을 통해 원래 문제에 대한 답을 계산한다. [Optimal Substructure]
   • 최적 부분 구조: 하위 부분 문제에서 구한 최적의 답이 합쳐진 큰 문제의 최적의 답을 구할 수 있는 구조

예를 들어, 피보나치 수열

재귀함수의 완전탐색으로 풀면 O(2^n)만큼 시간복잡도가 나온다.

Top-Down [재귀] - Memoization vs. Bottom-Up [반복문] - Tabulation

• Top-down
  • 재귀 사용 → 구현시간이 빠르다.
  • 재귀풀이에서 중복된 계산값을 저장하여 동일한 함수 호출 시에 재활용 한다.
  • hashtable 또는 list에 계산 결과를 저장한다.
• Bottom up
  • 반복문 사용 → 실행시간이 빠르다.
  • 더 작은 subproblem에 대한 계산결과를 DP table에 저장하여 더 큰 문제의 계산에 활용한다.
  • hashtable 또는 list에 계산 결과를 저장한다.

언제 동적계획법을 쓸까?

먼저 완전 탐색 알고리즘으로 접근해보고, 시간복잡도가 너무 높다면 DP를 적용할 수 있는지 생각해보자

subproblem의 중복 여부를 판단하는 것이 첫번 째 순서다.

1. Optimum value(최대최소), 방법의 개수 등을 구할 때
   • ~의 최소 비용은?
   • ~의 최대 이익은?
   • ~를 하는 방법의 개수는?
   • What is the longest possible ~
   • 특정 지점에 도달할 수 있는지?
2. 미래의 계산이 앞선 계산 결과에 영향을 받을때

출처: 인프런 코딩테크스 [ALL IN ONE]

https://leetcode.com/problems/min-cost-climbing-stairs/

Min Cost Climbing Stairs - LeetCode