ps:최솟값을_찾는_점화식의_최적화
최솟값을 찾는 점화식의 빠른 계산
- 문서 제목을 정하는게 제일 어려웠다; 대충 뭔 뜻인지는 알것이다..
- 내 느낌상 DP를 통해서 구해야 하는 문제의 90% 이상은 조건을 만족하는 답의 갯수를 구하는 문제 또는 조건을 만족하면서 가장 작은 점수를 갖는 답의 점수를 찾는 문제이다.
- 조건을 만족하는 답의 갯수를 구하는 문제의 변형으로는, 조건을 만족하는 K번째의 답을 구하는 문제가 있다
- 조건을 만족하는 가장 작은 답의 점수를 찾는 문제의 변형으로는, 점수가 아닌 답 자체를 출력하게 하는 문제가 있다. 보통 역추적이라고 말하는 것.
- 그럼 나머지 10%는 뭐지.. 다른게 있긴 한가? 뭐가 더 있을것 같긴 한데 당장 떠오르지는 않아서 그냥 대충 90%라고 해두겠다
- 암튼.. 답의 갯수를 구하는 문제는 DP[i]= sum_j(f(dp[0], …, dp[j])) 대충 뭐 이런식으로 나온다. 그리고 특수한 식에 대해서는 dp값을 0부터 i까지 차례차례 전부 채워서 DP[i]를 구하는 대신에, 빠르게 계산할수 있다. 대표적으로, f가 선형일때에는 선형 점화식의 빠른 계산법을 사용할수 있다.
- 그리고 본론인, 최솟값을 구하는 문제는 DP[i]= min_j(f(dp[0], …, dp[j])) 대충 뭐 이런식으로 나오는 경우이다.
- min
ps/최솟값을_찾는_점화식의_최적화.txt · 마지막으로 수정됨: 2023/02/19 03:58 저자 teferi
토론