Dynamic Programming (Fibonacci, Rod-Cutting Problem)

동적 프로그래밍이란, 복잡한 문제를 더 작은 하위 문제 단위로 나눠서 해결하는 알고리즘 설계를 말한다.

이렇게 보면 DP랑 분할 정복 divide and conquer랑 다를것이 없어 보이는데

분할 정복의 sub problem은 각각이 독립적이고,
DP의 sub problem은 서로 독립이 아니다.

DP는 sub problem을 한 번만 풀고, 해당 솔루션을 저장한 다음 재사용하여 중복 계산을 피한다.

 

해결하기 어려운 하나의 문제를 하위 문제로 나눠서 접근하는 것은 분할 정복으로 충분한데 DP를 배워야 하는 이유는
최적화 문제에 적용하기 위해서 이러한 개념이 필요하기 때문이다.
(물론 최적화 해법이 dp 하나만은 아니다. 여러가지 방법 중 하나)

 

 

---

 

 

동적 프로그램이 작동하는 방법

1. 하위  문제를  식별한다. 여기서 식별한 주요  문제를  더  작은  하위  문제로  나눈다. 
2. 솔루션  저장.  각  하위  문제를  해결하고  이를  테이블이나  캐시에  저장한다. 
3. 솔루션  구축.  저장된 솔루션을 기반으로 메인 문제에 대한 최적의 솔루션을 설계한다.

이렇게 솔루션을  저장하는 것으로, DP는 각 하위 문제가 한 번만 해결되도록 보장하여 계산 시간을 줄일 수 있다.

 

 

DP의 접근 방식에는 두 가지가 있다.

Top-down 접근은 Memoization, Bottom-up 접근은 Tabulation 이라고 한다.

 

 

이전에 재귀를 이용해서 피보나치를 풀었다.

재귀를 이용하면 중복되는 계산이 많았고, 동일한 입력과 sub problem이 있었다.

 

이번에는 Top-down 접근 방식인 Memoization(메모화)을 활용해서 풀어보자.

우선, main problem에서 부터 시작해서 이를 반복적으로 sub problem으로 나눈다.

중복되는 계산을 피하기 위해 sub problem의 답을 cache에 저장한다.

동일한 sub problem을 해결해야 할 때, cache에 저장된 답을 꺼내서 재사용한다.

이렇게 하면 sub problem을 한 번만 푸는 방식으로 시간 복잡도는 O(2^n)에서 O(n)으로 최적화시킬 수 있다.
하지만 n의 수가 너무 커지면 stack overflow 가 발생할 수 있다.
(일단은 재귀호출이니까 스택에 함수 호출이 쌓이고 있음. 중복 계산은 피해도 입력량이 너무 많으면 stack overflow 발생)

 

Bottom-Up 접근 방식인 Tabulation(표 작성) 으로도 해결할 수 있다.

sub problem (하단)부터 시작하여 점진적으로 main problem을 설계하는 방식이다.

sub problem에 대한 솔루션 표를 밑에서부터 채워나간다.

 

정리하자면 하향식 접근 방식(메모)은 상대적으로 작은 입력이 있는 문제에 적합하다. 만약 입력 크기가 크면 스택 오버플로우가 발생할 수 있다.
하지만 구현이 용이하고 코드가 쉬워서 덜 복잡하다.

상향식 접근 방식(표 작성)은 입력량이 많은 문제에 적합하다.
하지만 재귀 호출이 없어서(메모리 절약) 구현이 어렵고, 조건이 많아지면 코드가 복잡해진다.

 

 

 

---

 

 

 

Rod-Cutting Problem

길이가 n인 막대를 자르는 여러가지 방법 i = 1,2,.. 가 주어질 때, 잘라낸 막대 조각들을 판매함으로써 얻을 수 있는 최대 수익 r을 구하는 문제이다.

 

일반적인 재귀를 사용한다면 다음과 같은 형태일 것이다.

여기에서 p는 길이가 i인 막대의 가격이고
r은 길이가 i인 막대에 대한 최적 수익이다.

재귀에 대한 시간 복잡도를 구해보면 T(n) = 1 + 시그마 (0 ~ n-1)T(j) 가 나와서 결국 O(2^n)가 된다.

 

 

이제 하향식 접근 방법인 Memoization으로 풀어보자.

문제를 풀기 전에 sub problem이 계산된 문제인지 확인하고, 아니라면 그 결과를 배열에 저장한다.

 

상향식 방법 Tabulation은 sub problem부터 접근하여 이것을 표에 작성한다.

재귀 호출이 없음

이렇게 sub problem을 중복해서 계산하지 않을 수 있다.

 

DP를 이용한 문제 풀이에서 시간 복잡도를 구해보면, 일반 재귀와 확연하게 차이가 나는 것을 볼 수 있다.