동적계획법 솔루션

[1. 개요]

일반적인 접근 방식

• 완전 탐색에서 시작한다.
  => 완전 탐색 코드를 먼저 작성
  => 중복되는 문제에 대한 메모이제이션을 적용.
  
  
• 보통 중복되는 부분문제들을 최초 한번만 계산하고, 나머지는 이 값을 재활용 한다.
  => 메모이제이션
  => 최초 캐시 메모리는 -1 로 초기화 한다.
      (아직 이 부분 문제가 계산되지 않음을 의미한다.)
  => 캐시 메모리는 문제에서 주어진 공간 복잡도를 만족해야 한다.
• 메모이제이션 할 대상을 선정해야 한다.
  => 보통 캐시의 index 로 사용 함.
  => 부분 문제의 입력으로 주어지는 패턴을 갖는다.
  => 문제 입력의 범위를 보고 눈치껏 메모이제이션 할 대상을 선정해야 한다.
       => 특히, 캐시를 다차원 배열로 해야하는 경우

최적화 문제

=> 여러개의 가능한 답 중 가장 좋은 답을 찾는 문제

=> 최대 값, 최소 값 등을 찾는 문제라고 볼 수 있다.

• 최적화 문제에 특정 성질이 성립할 경우, 좀 더 효율적인 동적계획법을 작성 할 수 있다.
• 최적 부분 구조가 성립하는 경우
  => 각 부분 문제의 최적해만 있으면, 전체 문제의 최적해를 얻을 수 있다.
  => ex) 이번 부분 문제의 최대 값이, 전체 문제의 최대 값에 영향을 주는 경우.

반환 시 유의 할 점

• 부분 문제 해결 후 더하는(병합) 과정 에서 +1 등의 상수 값이 없는 경우
  => 기저 사례에서는 반드시 1 이상의 값이 반환되는 경우가 있어야 함.
  => 혹은, result = 1 + recursion(); 으로 계산해야 함.

반복적 동적 계획법

• 점화식을 세워야 하는 경우
  => 앞뒤로 살피면서 패턴을 찾아야 한다.
• 특정 경우에 대해서 답이 없음을 바로 알 수 있다.
  => 홀수 개의 퍼즐을 짝수 개의 사각형으로 채울 수는 없다.
• 재귀적 동적 계획법에서 메모이제이션을 위한 공간복잡도를 줄일 필요가 있는 경우 사용을 고려한다.
  => 슬라이딩 윈도우를 적용 할 수 있을 때,
• 단, 부분 문제간의 의존 관계를 고려하여, 계산 할 순서를 고민해야 한다.
• 구현 패턴
  => 기저 사례 작성
  => 계산 순서를 고려한 반복문 작성...
  => 꼭 앞에서 뒤로 이동할 필요는 없다. 뒤에서 앞으로 이동해도 된다. (단, 계산 순서...)
• 예제 (6), (7) 참조

완전 탐색 -> 메모이제이션 적용 시 유의점

• 재귀의 끝까지 가는 과정에서 메모이제이션에 잘못된 결과가 저장될 수 있다.
• 아래 예제 (4) 참조...
• 최적 부분 구조를 만들 수 있는 완전 탐색 방식인지 확인한다. (예제 5 참조)
  => 최적 부분 구조를 만들 수 없다면, 다른 방식의 완전 탐색이 가능한지 고민해봐야 한다.

---

[2. 예제]

1. https://testkernelv2.tistory.com/458
2. https://testkernelv2.tistory.com/515
3. https://testkernelv2.tistory.com/516
4. https://testkernelv2.tistory.com/519
5. https://testkernelv2.tistory.com/520
6. https://testkernelv2.tistory.com/521
7. https://testkernelv2.tistory.com/522
8. https://testkernelv2.tistory.com/523
9. a
10. a