최적화 문제 동적 계획법 레시피

1. 모든 답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계합니다.
2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꿉니다.
3. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄입니다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있습니다. 여기서 우리의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것입니다. 입력의 종류가 줄어들면 줄어들 수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한도로 활용할 수 있지요.
4. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션을 할 수 있도록 합니다.
5. 메모이제이션을 적용합니다.

경우의 수 계산하기 레시피

1. 모든 답을 직접 만들어서 세어보는 완전 탐색 알고리즘을 설계합니다. 이때 경우의 수를 제대로 세기 위해서는 재귀 호출의 각 단계에서 고르는 각 선택지에 다음과 같은 속성이 성립해야 합니다.
   a) 모든 경우는 이 선택지들에 포함됨
   b) 어떤 경우도 두 개 이상의 선택지에 포함되지 않음
2. 최적화 문제를 해결할 때처럼 이전 조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄입니다. 재귀 함수는 앞으로 남아 있는 조각들을 고르는 경우의 수만을 반환해야 합니다.
3. 메모이제이션을 적용합니다.

최적화 문제 답 계산하기 레시피

1. 재귀 호출의 각 단계에서 최적해를 만들었던 선택을 별도의 배열에 저장해둡니다.
2. 별도의 재귀 함수를 이용해 이 선택을 따라가며 각 선택지를 저장하거나 출력합니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)