[Algorithm] DP(Dynamic Programming) 동적계획법

동적계획법(DP) 이란? 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할때 사용하는 것 계산한 값을 저장해두는 메모리 장소 캐쉬(cache)에 저장하고, 답을 여러번 계산(중복)하는 대신 한번 만 계산해서 계산결과를 재활용함으로써 속도 향상을 꾀할 수 있는 알고리즘이다 * 그럼 분할 정복이랑 뭐가 다른건가요? 동적계획법과 분할 정복이 차이가 발생하는 부분은 문제를 나누는 방식이다 분할 정복은 단지 큰문제를 작은 문제로 나누어 푸는 것으로 중복된 것이 없다 동적 계획법은 어떤 부분 문제는 두개 이상의 문제를 푸는 데(반복이 일어남) 사용될 수 있기 때문에, 답을 여러번 계산 하는 대신 한번만 계산한다(중복된 것 활용) * 그럼 다른 dfs등 과 같은 재귀함수 쓰..