알고리즘 - 동적 계획법(Dynamic Programming)

큰 문제를 잘게 나누어 풀어놓고 그 해들을 이용해 큰 문제의 해를 찾는 방법.

 

1. 최적 부분 구조 : 문제의 답이 잘게 나눈 문제에 대해서도 답이어야함. 

2. 부분 문제 반복 : Top - Down or Down - Top 으로 문제를 나누어 내려올 수 있음. 큰 문제와 나눈 문제와의 풀이법이 같아야함.

 

똑같은 문제를 여러번 푸는 낭비를 막기 위해 "메모이제이션" 기법을 사용.

 

메모이제이션 : 미리 구해둔 정답을 메모해놓고 만약 다음에 같은 문제를 다시 풀어야 하면 불러와서 쓰는 방법.

 

대표적 예) 점화식.  등비,등차수열

 

하향식 방법 : Top - Down 방식으로 큰 문제를 계속 나누어 풀 수 있을 정도까지 나누고 문제를 풀어서 다시 올라가는 방식.

 

상향식 방법 : Down - Top 방식으로 작은 문제에서 시작해 큰문제가 될때까지 계속 합쳐 올라가는 방식.

 

둘중 하나만 가능한 문제들도 있으니 많이 풀어 보자.