최적화 문제 동적 계획법 푸는 방법 1. 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다. 2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 대해 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다. 3. 재귀 호출의 입력에 이전에 선택에 관련된 정보가 있다면 꼭 필요한 정보만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있다. (* 최적 부분 구조: 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 구할 수 있는 경우, 이 구조에 해당한다고 할 수 있다.) -> 이 부분에서의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것이다. 입력의 종류가 줄어들면 줄어들 수록 더 많은 ..