Dynamic Programming(동적 계획법 - dp)

다이나믹 프로그래밍이란?

 

 

Dynamic Programming 줄여서 DP라 부른다.

 

거창하게 보일 수 있지만,

문제를 어떤 형태로 변형시켜 쉽게 푸는 방법을 의미한다.

 

큰 문제를 작은 문제로 나누어서 푸는 알고리즘.

 

 

 

(조건)

 

• Overlapping Subproblem
  
  큰 문제가 작은 문제로 세분화될 수 있고, 같은 방법으로 풀릴 때,
• Optimal Substructure
  
  큰 문제의 정답을 작은 정답의 문제들로 구성할 수 있을 때,
  
  

대표적인 예) 

피보나치 수열,

-> 큰 문제를 작은 문제의 합으로 구할 수 있음.

 

공간 복잡도를 늘려서, 작은 답들을 기록하고 시간복잡도를 줄이는 그것은 이 기본적인 개념에 대한 이해가 끝나면,

그 때 다시 해보겠다.

 

 

(접근 방법)

 

1. Top - Down 방법
   
   큰 문제를 작은 문제들로 나누고, 작은 문제의 정답을 이용해서 큰 문제의 정답을 구하는 것.
   재귀함수 코드에 작은거부터 넣어서 구하는 것.
   
   보통 재귀함수일 경우엔 Top Down이 지배적이다.
   
   
   
2. Bottom - up 방법
   
   ㄱ. 크기가 작은 문제들부터 차례대로 푼다.
   ㄴ. 크기를 점점 키워나가며 푼다.
   ㄷ. ㄱ과 ㄴ의 과정을 반복하다보면, 문제의 정답을 풀 수 있다.
   
   
   

대부분의 Dp 문제는 두 가지 방법 모두로 정답을 구할 수 있다.

대표적인 dp 문제 뭐 얼마짜리 계산할건데 동전 갯주 젤 덜 쓰는 방법 구하는거.

(백준 -> 14916번)

 

 

점화식 생각하면 된다. 백준 DP 문제 모아둔거 풀어봐자.

14916

9095

2579

 

 

 

 

 

 

 

 

근데 이거만 보고 이게 욕심쟁이 알고리즘(Greedy Algorithm)이랑 뭐가 다르냐..

라고 할 수 있지만,

 

욕심쟁이의 경우 매 단계 단계마다 최선의 방법을 찾아서 선택하는 것이고,

 

DP의 경우 여러가지 방법을 검토하여 최적의 방법을 선택하는 것이니까 조금 다르다.