6D.1W-다이나믹 프로그래밍

다이나믹 프로그래밍(=동적 계획법)

다이나믹 프로그래밍:메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다
다이나믹 프로그래밍의 구현은 일반적으로 두가지방식(탑다운(하향식), 보텀업(상향식))으로 구성됨

일반적인 프로그래밍분야에서의 동적이란?
자료구조에서 동적할당은 "프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법"
반면에 다이나믹 프로그래밍에서 "다이나믹"은 별다른 의미 없이 사용된 것

다이나믹 프로그래밍의 조건

1.최적부분구조
:큰문제를 작은 문제로 나눌수 있고 작은 문제의 답을 모아서 큰 문제를 해결
2.중복되는 부분 문제
:동일한 작은 문제를 반복적으로 해결

->피보나치 수열: 앞의 두수의 합.

프로그래밍에서는 피보나치 수열을 배열이나 리스트를 이용해 표현(배열,리스트-테이블)

피보나치 수열이 계산되는 과정

피보나치 수열: 단순 재귀 소스코드(파이썬)

피보나치 수열의 시간 복잡도 분석

-단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다
-다음과 같이 f(2)가 여러번 호출 되는 것을 확인할 수 있다(중복되는 부분 문졔)

메모이제이션

다이나믹 프로그래밍을 구현하는 방법 중 하나
%한번계산한 결과를 메모리 공간에 메모하는 기법
-같은 문제를 다시 호출하면 메모했던 결과를 그대로 가지고 옴
-값을 기록해 놓는다는 점에서 캐싱(caching)이라고도 함

탑다운 vs 보텀업

탑다운(메모이제이션)방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 함.

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식임
-결과 저장용 리스트는 DP테이블 이라고 부름

메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미함
-메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아님
-한 번 계산된 결과를 담아 놓기만 하고 프로그래밍을 위해 활용하지 않을 수도 있음

피보나치 수열: 탑다운 다이나믹 프로그래밍 소스 코드(파이썬)

다이나믹 프로그래밍 VS 분할 정복

다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파익하기
1. 그리디, 구형,완전탐색 등의 아이디어로 문제를 해결할 수 있는가?
->다른 알고리즘 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려하자
2.재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운)작은 문제에에서 구한 답이큰 문제에서 그대로 사용될 수 있었으면, 코드를 개션하기
3.일반적인 코테에서는 수준에 맞는 기본 유형의 다이나믹 프로그래밍 문제가 출제