DP

 

📍 정의

값을 기록하고 참조해 중복 탐색을 하지 않는 것

- int형 1차원 배열 dp, 보통 -1로 초기화

- 시간 복잡도 : O(n)

 

 

📍 유형

- 가장 긴 증가하는 부분 수열 (LIS)

- 최장 공통 부분 수열 (LCS)

- 배낭 문제 (Knapsack)

- 연쇄 행렬 곱셈 알고리즘   (참고)

- 외판원 순회 문제 (TSP)    (참고1, 참고2)

- 이진 탐색 트리 (BST)

- 파도반 수열

 

 

📍 풀이 방법

 완전 재귀로 브루트 포스하게 풀기
→ 중복되는 함수 호출을 memoization을 통해 최적화 (시간 복잡도 : O(n))

(참고)

 

1) 재귀

2) 메모이제이션 ⇨ Top-Down 방식

3) Tabulation      ⇨ Bottom-Up 방식

 

- 최소 개수 찾는 문제, int 타입 배열을 큰 수로 초기화

- 최대 개수 찾는 문제, int 타입 배열을 작은 수로 초기화

 

 

 

➕ 그 外 참고 링크

[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍

알고리즘 - Dynamic Programming(동적 계획법)

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)