DP

다이나믹 프로그래밍(Dynamic Programming)

DP, 동적 계획법

 Overlapping Subproblem

  큰 문제와 작은 문제를 같은 방법으로 풀 수 있다

  문제를 작은 문제로 쪼갤 수 있다

 Optimal Substructure

  문제의 정답을 작은 문제의 정답에서 구할 수 있다

  두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법

  기본 전략은 문제를 작은 부분 문제로 나누는 것에서 부터 시작한다

  작은 부분 문제를 해결한 결과로 큰 문제를 해결할 수 있다

  특징은 중복되는 부분 문제들이 있다는 것

 적용 방법

  문제를 더 작은 부분 문제로 나눈다

  중복되는 작은 부분 문제는 한 번만 계산해서 그 결과를 저장

  중복되는 작은 부분 문제들은 여러 번 계산하지 않고 저장한 값을 이용

 메모이제이션(memoization)

  예) 재귀 함수 + 메모이제이션

  같은 입력에 대해 결과가 항상 같아야 한다

  같은 입력의 재귀 함수가 (매우 많이) 중복해서 호출된다

  예, 피보나치 수

구현 방법

재귀 호출을 이용하는 방법

 Top Down

    문제를 작은 문제로 쪼개고, 그 중 한 조각을 해결한 다음 나머지 작은 문제를 같은 방법으로 해결한다

  장단점

   구현이 직관적이고 이해하기 쉽다
 
   전체 부분 문제 중 일부의 답만 필요할 경우 더 빠르게 동작한다

   Sliding window 를 사용할 수 없다

   스택 오버플로우를 조심해야 한다

   Code pattern (문제해결전략 참조)


반복문을 이용하는 방법

Bottom Up

    문제 해결에 필요한 가장 작은 문제를 해결하고, 문제를 조금씩 크게 만들어 가면서 해결한다

  장단점

구현이 대개 더 짧다

재귀 호출 보다 조금 더 빠르다

Sliding window 를 사용할 수 있다

구현이 비직관적이고, 이해하기 어렵다

부분 문제들을 해결하는 순서에 신경을 써야 한다

가장 유명한 예는 이항 계수(binomial coefficient)의 계산

이항 계수 C(n, r) 는 n 개의 서로 다른 원소 중에 r 개의 원소를 순서 없이 골라내는 방법의 수를 나타내는 것

점화식: C(n, k) = C(n - 1, k - 1) + C(n-1, k)



함수의 반환 값이 그 입력 값만으로 결정되는 참조적 투명 함수(referential transparent function)의 경우에만 메모이제이션이 적용가능하다