동적 프로그래밍 (Dynamic Programming: DP)

동적 프로그래밍 (DP)

 

: 큰 하나의 문제를 여러 하위 문제로 나누어 풀고 그 결과들을 결합해서 최종 목적인 큰 문제를 해결하는 방식의 알고리즘.

 

💡 반복적인 처리(계산)를 피할 수 있음  ☞ 이전 단계 처리 결과를 저장하고 다음 단계를 해결할 때 이미 진행했던 부분은 저장되어 있던 값을 불러옴

💡 점화식을 세우면 쉽게 DP 문제 해결 가능 (ex. 피보나치수열 점화식 : dp[i] = dp[i-1]+dp[i-2] )

💡 어떤 값을 어떤 방식으로 저장할지 정하는 것이 포인트!!

 

 

<적용방법>

1. Top-Down:  말 그대로 문제풀이가 위에서 아래로 진행 > 주로 재귀 함수 사용 > 시간 복잡도 문제가 발생할 수 있고 저장 유무에 따라 DP로 보지 않는 의견도 있음

2. Bottom-Up: 반대로 문제풀이가 아래에서 위로 진행 > 반복문 사용 > 진정한 동적 프로그래밍 방식

 

 

참고 문제 : https://leetcode.com/problems/uncrossed-lines/