다이나믹 프로그래밍(dynamic Programming)

출처:www.youtube.com/watch?v=5Lu34WIx2Us

 

<다이나믹 프로그래밍>

- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

- 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(Top-down(하향식), Bottom-up(상향식))으로 구성

 

- 동적 계획법이라고도 한다.

- Dynamic?

    (자료구조) 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'

    (알고리즘) 의미없음

 

- 특정 문제가 다음 조건을 만족할 때 사용 가능

    1. 최적 부분 구조(Optimal Substructure)

      : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음

    2. 중복되는 부분 문제 (Overlapping Subproblem)

      : 동일한 작은 문제를 반복적으로 해결해야 함(부분문제가 중첩되어 반복, 동일한 문제를 반복적으로 해결)

- 문제가 위 조건에 맞는지 확인한 다음 dp적용

 

ex. 피보나치 수열

-> 재귀로 구현할 경우 지수 시간 복잡도를 가지게 됨(중복되는 문제)

점화식: 인접한 항들 사이의 관계식

 

<메모아이제이션(하향식, Memoization)>

- dp를 구현하는 방법 중 하나

- 한 번 계산한 결과를 메모리 공간에 메모하는 기법

    : 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다

    : 값을 기록(배열 등에)해 놓는다는 점에서 캐싱(Cacheing)이라고도 한다.

 

<bottom-up>

- 반복문 이용

- dp의 전형적인 형태

 

<다이나믹 프로그래밍 vs 분할 정복>

- 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있음

    : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

- 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복

    : 다이나믹  프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨

    : 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음

 

 

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

- 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요

- 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있음

    : 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 DP를 고려해보자

- 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다.