한줄요약

→ memoization 을 적용해 푸는것을 말한다.

개요

DP 동적계획 다이나믹 프로그래밍 알고리즘 설명 10분만에 이해하기 (정수 삼각형 문제풀이)

다이나믹 프로그래밍(DP)는 완전탐색, DFS, BFS 를 통해 경우의 수를 계산해야 되는데, 경우의 수가 너무 많아 속도가 느려지는 문제를 개선하고자, 수행시간을 단축하고자 해서 만들어진 알고리즘이다.

DP 알고리즘이 없던 시절에는 모든 조합을 다 만들어 보는 수밖에 없었다.

DP 알고리즘이 생긴 이후로는 불필요한 계산을 줄이고, 효율적으로 최적해를 찾을 수 있게되었다.

DP 알고리즘은 주로 두 가지 방식으로 구현된다.

1. 상향식 접근법 (Bottom-Up Approach): 가장 작은 하위 문제들부터 시작하여 점차적으로 더 큰 문제들로 나아가며 해결합니다. 이 방식에서는 일반적으로 반복문을 사용하여 문제를 푼다.