동적프로그래밍
- 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결함
- 부분 문제가 서로 중복될 때, 부분 문제가 다시 자신의 부분 문제를 공유할 때 적용
동적 프로그래밍의 적용조건
- 최적 부분구조
큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션 포함 - 재귀호출시 중복
재귀적 해법으로 풀면 같은 문제에 대해 재귀호출이 심하게 중복됨
=> 동적프로그래밍으로 해결!!
- 일반적으로 최적화 문제에 적용
- 다양한 해를 가질 수 있는 문제에서 최적(최대,최소)값 구하는 문제
- 최적을 가지는 해가 여러개 존재할 수 있음
동적프로그래밍 알고리즘 개발단계
- 최적해 구조의 특징을 찾음
- 최적해 값을 재귀적으로 정의함
- 최적해 값을 일반적으로 상향식(bottom-up) 방식으로 계산함
- 계산된 정보들로부터 최적해를 구성함
막대자르기
강철 막대를 작게 나눠서 판매
자르는데 비용 X
이익이 최대가 되도록 막대를 자르는 방법 ?
막대의 길이마다 가격이 다름
길이 i일때 pi
막대 길이가 i면 연결되는 부분이 i-1개 부분이 발생하므로 그 부분을 자르냐 자르지 않느냐 2가지 경우가 있어서 총 2i-1의 경우의 수가 있음
i=4인 경우 예시인데 2개 2개로 나눠서 5+5=10 을 받는게 가장 비싸게 받을 수 있다
길이가 n인 막대를 1<=k<=n인 k조각으로 나눌 수 있다.
k조각의 막대 길이를 각각 i1~ik라고 하고 각 조각의 가격이 p1~pi라 하면
길이 n인 막대의 가격 rn = p1+p2+p3...+pi가 됨
길이 n인 막대의 최대 수익 rn은 더 작은 막대로부터의 최대 수익을 통해 나타낼 수 있다
rn = max(pn , r1+rn-1, r2+rn-2 .... , rn-1+r1)
즉 n인 막대를 길이 i랑 n-i로 잘라서 각 길이에 대한 최대 수익 ri + rn-i 의 값을 더하면 되는데 어떤 i가 수익을 최대로 하는지 일일히 구해야함
즉 길이 n인 막대를 잘라서 i, n-i 길이가 되었으면 각각 i, n-i인 막대에 대해 문제를 푼다고 생각하면 된다.
막대길이 n, 각 길이마다 가격정보가 있는 배열 n에 대해 이렇게 재귀적으로 풀수있음
하향식 재귀로 풀면 i=1일때 나머지 조각이 길이 3이니까 3의 최적해를 구하는 과정에서 2의 최적해를 구하게 되고 i=2이면 나머지 조각 길이 2니까 2의 최적해를 구하는 과정이 또 반복됨
-
동적프로그래밍으로 풀면 부분 무제를 풀고 해를 저장해서 다시 풀어야 하면 저장한 값을 가져다 쓴다
-
하향식 방법
재귀적으로 작성하는건 같지만 저장해 놓고 이미 구했으면 확인해서 그 값을 가져다 쓰고 아닐 경우 그냥 계산함
- 상향식 방법
처음에 그냥 모든 부분문제를 풀어놓고 저장한다음 가져다 쓴다
- 하향식 방법
- 상향식 방법
길이 n일 때 최적 가격 r[n]을 구해야함
그러기 위해 n을 j, n-j로 나누는데 j=1부터 시작함
j는 또 i랑 j-i부분으로 나눠서 r[j]의 최적 가격을 구함
이 때 재귀적으로 구하지 않고 이미 r의 값을 이용함
i=7일때를 보면 7은 1,6/2,5/3,4로 나눌 수 있는데 3,4로 나눈 경우가 최적값이고 이 때 3,4의 값은 이미 구해놓은 값을 사용함
최적가격 배열 r 뿐만 아니라 최적가격에 이르게 하는 자르는 위치 s 배열도 반환함
