동적 계획법

동적 계획법(Dynamic Programming)

• 분할 정복 기법과 많은 부분이 비슷함.
• 같은 부분 문제를 다시 풀지 않도록 하는 것이 핵심
  ex)한번 푼 문제의 답을 저장하고 다음에 다시 풀어야 할 때는 그 문제에 대한 해답만 이용하는 방법
• 메모이제이션(Memoization)
• 문제를 풀 떄마다 이미 풀린 문제인지를 먼저 확인하는데, 풀린 문제이면 저장된 답을 이용하고 풀리지 않은 문제이면 그 문제를 풀고 답을 저장한다.
• 하향식(Top-bottom)식으로 문제를 해결
• 테이블화(Tabulation)
• 결과를 저장할 테이블을 먼저 만든다. 다음으로 답이 이미 알려진 상황인 기반 상황(Base Case)에 대한 테이블 항목을 먼저 채우고, 이를 바탕으로 테이블을 채워 올라간다.

동적 계획법을 이용한 문제 해결 전략

• 동적 계획법을 적용하려면 아래의 같은 두 가지 특성을 가져야 함.
• 겹치는 부분 문제(Overlapping subproblem)
• 동일한 부분 문제들이 중복해서 발생하는 것.
• 최적 부분 구조(Optimal Structure)
• 부분 문제의 최적해들을 이용하면 전체문제의 최적해를 구할 수 있는 구조를 의미함.
• 메모이제이션과 테이블화를 동시에 사용 가능할 경우
• 순환 호출의 부담이 없는 테이블화가 시간적으로 좀 더 유리함.
• 테이블을 함수 밖에서 생성할 필요가 없으므로 코드의 모듈화에서도 유리함.
• 어떤 부분 문제가 먼저 해결될지 예측하기 어려운 경우라면 메모이제이션이 유리함.