[알고리즘] Dynamic Programming

한달동안 알고리즘문제에 손도 안댔더니.. 다 까먹어버린것같다.. 큰일났다..

DP (Dynamic Programming)이란?

• 큰 쿤제를 작은문제로 나누어 푸는것
• 동적 기억하기 프로그래밍 이라고 이해하는편이 좋겠다.

DP와 분할정복의 차이

• 작은문제가 중복이 일어나는가 안일어나는가
  • 분할정복 : 큰 문제를 작은문제로 나누어 푸는것은 맞지만, 작은문제들에서 반복이 없다!!
  • DP : 작은문문제들이 반복되는것 (답이 바뀌지 않는)

DP 적용방법

• 모든 작은문제는 한.번.만 푼다. -> 한번 구한 답을 어딘가 저장해놓는다.
• 이후에 다시 반복되는 작은문제가 나타나면 이미 구한답을 그대로 이용한다.

DP의 조건

아래와 같은 조건을 만족하는 경우에 다이나믹 프로그래밍 풀이를 적용할수 있다. 

DP문제는 이 문제가 DP로 푸는것인가? 를 아는것이 어려운것 같다. 공식처럼 잘 기억하고 있다가 이런 형식의 문제를 만나면 먼저 DP로 풀수있는가? 하고생각하는 힘을 길러야겠다.

• 작은문제가 반복되는 경우
• 같은 문제는 구할때마다 답이 같은경우

구현 방법

Bottom-up

• 작은문제부터 차근차근 구해나가는 방법 ( 아래에서부터 위로 )
• 코드 가독성이 좋지만 작성하기 어려울수있음

Top-down

• 큰 문제를 풀다가 작은문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결해나가는 방법
• 재귀함수로 구현하는 방식
• 풀기는 쉽지만 소스 가독성이 떨어질수 있음 

 

DP문제는 위에서도 말했듯 이 문제가 DP로 풀리는 문제인지를 먼저 인지하는것이 중요하다.

어떤 큰 문제가 있을때, 작은 단위의 문제로 생각하는데, dp[0], dp[1], dp[2]와같이 작은문제를 해결하다보면 

이후에 dp[4]즈음에 이전에 구해놓은 작은 문제들인 dp[0],dp[1],dp[2],dp[3]을 이용해 점화식을 도출해낼수 있다.

 

 

 

 

참고링크 :

https://galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?