자료구조 여름방학 4주차

섹션 9

동적 계획법(DP, 다이나믹 프로그램)

복잡한 문제를 여러개의 간단한 문제로 분리하여 해결하는 것

 

point..

큰 문제를 작은 문제로 나눌 수 있어야함

작은 문제들의 결과값이 항상 같아야함

작은 문제들을 최초의 한번만 계산하고 DP 테이블에 저장

다시 같은 작은 문제가 발생했을 때 다시 계산하는 것이 아니라 테이블에 저장 된 값을 활용

 

ex(피보나치 수열)

 

a(n+3)=a(n+1)+a(n+2)

수열을 구하기 위해 모든 값을 계산하는게 아니라 점화식을 이용하여 계산함

동적 계획법으로 풀이할 수 있는가?

== 작은 문제로 나눌 수 있나? 값이 항상 같은가?

 

6번째 피보나치 수열의 값은 5번쨰 피보나치 수열의 값+4번쨰 피보나치 수열의 값

수열의 값은 항상 같음

 

동적 계획법으로 풀이 가능하고 수열의 값은 항상 같은

 즉 동적 계획법으로 풀이 가능.

 

이제 점화식을 세울 차례

 

dp테이블 .. 배열의 형태를 이용하여

d[n]=d[n-1]+d[n-1] 로 점화식을 세울 수 있음.

 

top down 방식을 풀이

 

6번쨰 값을 구하기 위해 4번쨰, 5번째 값을 구하고 4번째를 위해 3번째, 2번째를 구함. 1번쨰와 0번쨰의 값은 이미 저장된 값으로 이용함.

 

3번째 값을 구하기 위해 2번 1번 값을 사용하는데 이떄 이용되는 2번 값은 4번을 구하기 위한 과정에서 이미 계산된 값임!

이때는 직접 구하지 않고 저장된 값을 가져다가 쓴다.

  

top down 방식으로 구현하기

 

재귀함수 형식으로 구성.이미 계산한 적 있는 값은 재귀로 호출 하되 다시 계산하지는 않음. 이를 위한 dp테이블 사용.

가장 작은 문제(이미 아는 값 따로 저장)