알고리즘/DP
2021. 7. 13.
기초 DP 최적화
DP를 최적화 하는 방법들에 대해 알아봅시다. https://anz1217.tistory.com/19 동적 계획법 (Dynamic Programming) 동적 계획법 (이하 DP)은 큰 문제를 분할하여 부분 문제들로 만든 다음, 각 부분 문제의 답으로부터 전체 문제의 답을 이끌어내는 방식의 알고리즘입니다. 그런데 이 정의 어디에서 본 적이 있는 anz1217.tistory.com 제 예전 글에서도 설명한 바 있지만, DP로 문제를 해결하는 방식과 시간복잡도 계산에 대해 다시 한번 생각해봅시다. DP는 큰 문제들을 작은 부분 문제로 나누어 푸는 중, 서로 겹치는 부분 문제가 존재한다면 이를 한 번 씩만 계산하도록 Memoization하여 푸는 방식입니다. 요약하면 모든 문제를 많아도 1번씩만 해결하게 되므..