Dot Algo∙ DS/알고리즘 개념
2021. 3. 9.
[알고리즘] 동적계획법 DP (Dynamic Programming) 정리 (Java)
동적계획법 Dynamic Programming 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로, 이름만 가지고는 무엇을 의미하는지 영 알 수 없기 때문에 가장 많은 오해를 불러 일으키는 주제이기도 하다. Dynamic? 동적? 기억하기? 자료구조의 동적할당(Dynamic Allocation)에서 '동적'은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. 그러나, 알고리즘의 동적 계획법(Dynamic Programming)에서 '동적'은 별 뜻 없다 그냥 '기억하기'라고 생각하면 편하다. '프로그래밍'은 컴퓨터 프로그래밍이 아니라 테이블을 만든다는 뜻이다. 중복되는 부분 문제 피보나치 수열을 코딩하려고 한다. 점화식이 F(n) = F(n-..