[이론] 동적프로그래밍

동적 프로그래밍

하나의 문제를 작은 단위로 쪼개어 해결하고 결과를 수집 및 병합하여 최종 결론을 만들어내는 일련의 과정

• 프로그램 해결과정에서 연산의 결괏값을 저장하고
• 그 이후에 중복된 연산의 저장된 값을 꺼내어 쓸 수 있다.

하위문제가 여러개로 구성된다.

dp 라는 일종의 리스트에 데이터를 저장한다. : 메모이제이션

>>>> 점화식!!! 

→ 중복 연산이 안 생기게 한다.

초기화를 -1로도 하는구나

• 동적 프로그래밍 문제 특징
  • 모든 경우의 수를 파악해서 진행하면, 지수승의 시간 복잡도를 지님
    • 모든 경우의 수를 조합하면서 확인하는 과정을 가지는 문제
  • sort, 이진탐색 → X
  • 키워드 : shortest, longest, minimized ,maximized, least, most, fewest, greatest, biggest, smallest
  • 최대 구간의 합
• 연습방법
  1. 브루트포스로 풀기
  2. 풀이를 분석하여 반복되는 작업 정리
  3. 전체 탐색에서 하위 문제로 쪼개어보고 반복되는 단계있는지 탐색

가변 변수가 몇개인지 확인하고, 그걸로 dp 짜기

• 가변 변수 1개 → 1차원 list
• 가변 변수 2개 → 2차원 list

개발 코드 작성 시 추가 부분

1. 재귀
2. 검사 (index ≤ 0 시 out)
3. 초기화 된 거는 그냥 반환

• 구분유형
  • top down → 재귀법
  • bottom up → 반복법