동적 프로그래밍(Dynamic Programming) - DP

1. 동적 계획법 (Dynamic Programming)이란?

 

• 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말
• 하나의 문제는 단 한번만 풀도록 하는 알고리즘

2. 분할 정복과 차이점

 

* 분할 정복

 

- 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법

- 작은 문제에서 반복이 일어나는 부분이 없음

 

* 동적 프로그래밍

 

- 작은 부분 문제들이 반복되는것을 이용해 풀어나감

 

 

3. Dynamic Programming 방법

 

- 모든 작은 문제들을 한번만 풀어야 한다.

- 푼 작은 문제의 정답을 어딘가에 메모해 놓음

- 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한

  작은 문제의 결과값을 이용

 

* 조건

 

• 작은 문제가 반복이 일어나는 경우
• 같은 문제는 구할 때마다 정답이 같음

=> 위의 조건을 만족하는 경우에만 동적프로그래밍을 사용할 수 있다. 

 

 

4. Memoization

 

- 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써

  동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

 

ex) 피보나치 수열 -  1 , 1 , 2 , 3 , 5 , 8 , ... => f(n) = f(n-1) + f(n-2)    (n>=2)

 

위와 같은 점화식을 갖기 때문에 재귀 함수를 통해 간단하게 구현할 수 있지만 n이 증가함에 따라

호출되는 함수의 수가 기하급수 적으로 증가하기 때문에 일정 수 이상의 순열을 구하기 어려움

 

 

* 동적 계획법의 조건 2가지 상기

 

1. 작은 문제들이 반복

2. 같은 문제는 구할때 마다 정답이 같음

 

=> 위 두가지 조건을 만족하기 때문에 동적 계획법 적용 가능

 

* 동적 계획법 Code (C++) - Top down

 

DP사용 X

피보나치 수열은 수열이 1개만 늘어나도 계산 량은 2배가 늘어나기 때문에 50번째 피보나치 수열을 계산하는

연산량은 2의 50제곱으로 볼 수 있다.

대략 1,000,000,000,000,000개 이상의 계산을 처리 해야함. => DP 활용

 

 

DP 사용 O

 

한번 계산한 값을 배열에 저장하여 다시 써야할 상황이 오면 함수를 호출하지 않고 배열안에 있는 값을

그대로 사용하여 연산량을 줄일 수 있음.   => Memoization

 

 

* 동적 계획법 Code (C++) - Bottom up

 

1. 직관적으로 풀 수 있는 작은 문제는 풀어놓음

2. 점화식을 이용하여 반복문을 돌림. 작은 문제에서 구한 해를 이용하여 큰 문제를 풀기 때문에

    시간 복잡도를 줄일 수 있음

 

 

* Top-down vs Bottom-up

 

• Top-down방식에 Memoization을 활용했다는 가정하에 시간 복잡도는 같음
• 하지만 실제 걸리는 시간은 Top-down dp가 더 길다고 일반적으로 알려져 있음
• 재귀DP의 장접은 점화식 그대로 호출이 되기 때문에 형식/순서에 얽매이지 않음
• for문 DP의 장점은 시간이 적게 걸림
• 따라서 문제에 따라 둘 중 어느 방법을 활용할지 알아야함

 

 

 * 요약

 

1. DP는 큰 문제를 작은 문제들로 분할하여 그것을 이용해 큰 문제를 해결하는 방법

2. 분할정복과 다른점은 DP의 경우 작은 부분 문제의 답이 항상 같음

3. 문제를 풀 때 시간복잡도를 고려하여 top-down과 bottom-up중 선택해야함