DP
📍 정의
값을 기록하고 참조해 중복 탐색을 하지 않는 것
- int형 1차원 배열 dp, 보통 -1로 초기화
- 시간 복잡도 : O(n)
📍 유형
- 배낭 문제 (Knapsack)
- 연쇄 행렬 곱셈 알고리즘 (참고)
- 외판원 순회 문제 (TSP) (참고1, 참고2)
- 이진 탐색 트리 (BST)
- 파도반 수열
📍 풀이 방법
완전 재귀로 브루트 포스하게 풀기
→ 중복되는 함수 호출을 memoization을 통해 최적화 (시간 복잡도 : O(n))
(참고)
1) 재귀
2) 메모이제이션 ⇨ Top-Down 방식
3) Tabulation ⇨ Bottom-Up 방식
- 최소 개수 찾는 문제, int 타입 배열을 큰 수로 초기화
- 최대 개수 찾는 문제, int 타입 배열을 작은 수로 초기화
➕ 그 外 참고 링크
[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍
안녕하세요, 이번 시간에는 다이나믹 프로그래밍을 다룹니다. 직전까지 막 재귀, 백트래킹, 정렬 이런 것들로 되게 고통받으셨을텐데 오늘껀 개념도 그렇게 어렵지 않고 구현 난이도도 낮아서
blog.encrypted.gg
알고리즘 - Dynamic Programming(동적 계획법)
1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로
hongjw1938.tistory.com
[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)
목차 다이나믹 프로그래밍이란? 다이나믹 프로그래밍 (Dynamic Programming) 또는 동적 계획법은 큰 문제를 작은 문제로 쪼개서 푸는 기법이다. 다이나믹 프로그래밍의 특징은 모든 작은 문제들은 단
propercoding.tistory.com