문제 추가! Quiz Request: (C++ 동적계획법 구현)

[qodydgk8624]

이 템플릿은 한국어와 영어로 쓰여 있습니다. This template is both written Korean and English.

(꼭, 이슈 하나당 하나의 문제만 적어주세요! Please write only one question per issue!)

문제의 언어 Quiz Language (Programming Language)

e.g. Cpp

문제 Question (OX로 문제를 풀수있어야 합니다 Yes/No quiz)

(DP란 Dynamic Programming를 정의하도록 한다.) DP에서 특정 문제를 explicit formula 로 나타낼 때 '점화식을 세운다' 라고 정의한다. DP의 점화식을 찾아주는 Berlekamp_massey Algorithm 이 있다. 이 문제에서는 C++ only iostream imported 를 기준으로 한다. 그렇다면 점화식 크기가 k일때 시간복잡도는 O(nk+n log mod)[O(n^2)] 이다.

답 Answer

• [x] O

풀이 Answer Explanation

berlekamp_massey algorithm은 수열을 입력받아 수열에 만족하는 기본적인 점화식인 Dn=∑k,i=1(Dn−i×Ci) 을 찾을 수 있다. 이런 점화식은 Linear recurrence이다. 하지만 점화식이 복잡하더라도 DP 상태 전이가 행렬로 표현 가능하면 , DP에 해당하는 linear recurrence existence가 보장된다. 그러므로 O(n^2)이라 할 수 있다. 증명은 Cayley-Hamilton theorem을 참고하면 된다. 이 알고리즘은 'Find determinant of matrix X' 에 대해서 자주 쓰인다. 또한, C++ DP PS ( Problem Solving )에 자주는 아니지만 간편하게 사용할 때 쓰인다. (p.s. 점화식 찾기 힘들 때 종종 코드 복붙해서 줏어먹기를 하기도 한다.)

사진 (선택) Image (Optional)

사진 설명 Image Description

[pmh-only]

문제와 풀이는 초보자도 알수있도록 간단하고 명료해야 합니다 또한, 예제 코드를 보여준다면 더 좋습니다 수정후 다시 올려주세요