DP 정복 - 4.2 다이내믹 프로그래밍을 사용한 문제 해결

재귀 호출이나 메모 전략은 실행 시간 또는 사용 메모리 관점에서 최적의 풀이법이 아닐 수 있음.

어떤 문제에 시간 또는 메모리 제한이 주어지면 반드시 다이내믹 프로그래밍 또는 다른 최적화된 풀이법을 찾아야 할 수도 있음.

 

다이내믹 프로그래밍 적용 가능한지 파악하기

- 문제가 최적의 하위 구조를 가지고 있는지 확인.

- 하위 문제를 반복해서 계산하는지를 찾아봄.

- 최적화, 최대화 또는 최소화나 어떤 작업의 경우의 수를 구하는 유형의 문제인지 확인.

 

다이내믹 프로그래밍으로 문제 풀기

- 세상에 똑같은 문제는 없기 때문에 모든 다이내믹 프로그래밍 문제에 적용할 수 있는 '마법의 은탄 환' 같은 방법은 없음. (아놔 ㅠㅠ)

- 그러나 아래의 단계식 접근 방법은 적용해 볼 수 있음.

1. 다이내믹 프로그래밍을 적용할 수 있는 경우인지 확인(위에 소개)

2. 점화식 또는 재귀 과정을 정의 : 같은 종류의 하위 문제가 있다면 재귀 호출 사용 가능

 2-1. 문제를 하위 문제를 사용해 하향식으로 정의 : 이 시점에 시간 복잡도는 고민하지 않아도 됨.

 2-2. 맨 아래에 해당하는 '기본 경우'에 대한 답을 정의 : 나머지는 재귀 호출에 맡김. 하위 문제들은 대부분 재귀 호출에 의해서 해결되는데 제일 끝(가장 기본의 경우)의 답은 함수가 해결해야 함.

 2-3. 종료 조건을 추가 : 재귀 과정을 어디선가 반드시 멈춰야 함. 그 어디선가가 종료 조건. 대부분 기본 경우가 종료 조건에 해당.

3. 메모 전략을 시도 : 같은 하위 문제를 반복해서 계산하는 경우라면, 하위 문제의 해답을 캐시에 저장한 후 문제를 풀어야 할 때 캐시에 저장된 값을 사용. 숙련이 된다면 이 단계는 건너뛰어도 됨.

4. 상향식으로 문제 풀이에 도전 : 마지막으로 재귀 호출을 제거하고 기본 경우에서 출발하는 진행 반향으로 풀이법을 재정의. 문제를 풀어가는 동안 전체 문제를 푸는 데 필요한 결과들만 캐시에 저장.

 

다음 포스팅부터는 예제 문제를 풀어보는 걸 해볼 예정!