다이내믹 프로그래밍(DP, 동적 프로그래밍) 1분 요약 정리

다이내믹 프로그래밍

• 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다.
• 한 번 계산한 문제를 다시 풀어야 하는 비효율적인 알고리즘을 개선할 수 있다.

 

다이내믹 프로그래밍의 목적

• 메모리를 사용하여 중복된 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선한다.

 

다이내믹 프로그래밍 사용 고려

• 완전탐색, DFS, BFS 등은 동일한 문제를 다시 푸는(만들 수 있는 모든 조합을 전부 따져봐야 하는) 단점을 가지고 있다. 이미 계산한 문제를 반복적으로 다시 풀어야 하는 비효율성이 보인다면 다이내믹 프로그래밍을 고려하는 것이 좋다.

 

다이내믹 프로그래밍으로 풀어야 하는지 판단할 수 있는 기준

1. DFS/BFS로 풀 수 있지만 경우의 수가 너무 많은 문제
2. 경우의 수를 계산할 때 중복 연산이 많은 문제

 

다이내믹 프로그래밍의 사용 조건

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 답이 이를 포함하는 큰 문제에서도 동일하게 적용된다.

 

정리

• 다이내믹 프로그래밍은 상당한 양의 문제를 먼저 작은 크기로 나눠 해결하면서 나아가 전체의 답을 구한다.
• 다이내믹 프로그래밍이 분할 정복과 다른 점은 이미 계산한 결과를 배열에 저장하여 나중에 동일한 계산이 필요할 때 저장된 값을 반환하는 방식으로 불필요한 반복 계산을 줄일 수 있다는 것이다.

 

 

참고

https://www.youtube.com/watch?v=0bqfTzpWySY

https://www.youtube.com/watch?v=FmXZG7D8nS4