Python for Algorithms-DP&Merge

Dec 28, 2022

• 동적 계획법 (DP)
  1. 최적화 문제 풀이 레시피
  2. 재귀적 동적 계획법
  3. 반복적 동적 계획법

Python for Algorithms-DP

동적 계획법 (DP)

전체적으로

1. 완전 탐색 구현
2. 메모이제이션 구현
   을 통해 풀어낸다.

최적화 문제 풀이 레시피

최적 부분 구조인 문제의 경우 DP를 이용해 최적의 결과를 얻을 수 있다.

• 최적 부분 구조 : 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어 낼 수 있는 구조
  1. 최적의 답을 구하는 완전 탐색 알고리즘 설계
  2. 일부 선택된 부분만의 최적의 답을 구하는 부분 문제로 바꾸기
  3. 재귀 호출 시 넘길 입력 인자를 선택
  • 완적한 최적 부분 구조일 경우 완전히 입력을 없앨 수도 있으며, 입력을 줄어들 수록 많은 부분 문제가 줄어들어 효율적이다.
    1. 메모이제이션 구현
  • 입력이 문자열, 배열 등 저장에 비효율적인 구조의 경우, 효율적인 정수형 등으로 바꿀 수 있도록 변환해보자.

재귀적 동적 계획법

반복적 동적 계획법