[Algorithm] (이코테) DP 정리

DP(Dynamic Programming)

목적

재귀함수를 계산할 때 같은 값을 매번 계산해야 하는 상황을 방지하자

조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

종류

1. TOP-DOWN 탑다운 방식

• 재귀함수 사용
• 큰 문제를 해결하기 위해 작은 문제를 호출
• Memoization(메모이제이션)
  한 번 계산된 결과를 메모이제이션 하기 위해 리스트를 사용하고 이미 계산한 적 있는 경우는 그 값을 계산하지 않도록 캐싱(Caching)

2. BOTTOM-UP 보텀업 방식 (전형적인 방법)

• 반복문 사용
• 작은 문제부터 자근차근 답을 도출
• 저장용 리스트 : DP 테이블

방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악

1. 재귀함수로 비효율적인 탑다운 프로그램을 작성하고 작은 문제에서 구한 답이 큰 문제에서 그대로 사용된다면 메모이제이션으로 개선하기
2. 가능하다면 보텀업 방식으로 구현할 것(재귀함수 스택크기 한정될 가능성 있기 때문에)

tip : 오천 번째 이상의 큰 피보나치 수를 구하도록 하면 recursion depth(재귀 함수 깊이)와 관련된 오류가 발생할 수 있기 때문에 sys 라이브러리에서 setrecursionlimit()함수로 재귀 제한을 완화할 수 있음

References

이것이 코딩 테스트다 - 나동빈 저