[Algorithm] Dynamic Programming
동적 프로그래밍이란? 문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘 문제 풀이 순서 문제가 원하는 정답을 찾기 위해 가장 먼저 완전 탐색(Brute-Force Search) 접근을 시도한다. 근데, 완전 탐색 과정에서 탐색하게 되는 경우가 지나치게 많아서 도저히 안 될 것 같다. 이럴 때, 모든 경우를 빠르게 탐색하는 방법으로 동적 프로그래밍 접근을 시도한다. 동적 프로그래밍 접근 순서 풀고 싶은 가짜 문제 정의 가짜 문제를 풀면 진짜 문제를 풀 수 있는가? 초기값은 어떻게 되는가? 점화식 구해내기 진짜 문제 정답 출력하기 예제 피보나치 수열 가짜 문제 정의 D[i] : i 번째 까지 피보나치 수열의 합. 진짜 문제를 풀 수 있는가? ..
Data Structure & Algorithm
2023. 8. 27. 14:43
