[Algorythm-개념] 동적 계획법

1. 동적 계획법이란?

동적 계획법(dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
- wikipedia

*DP라고도 불림

 

2. 동적 계획법 등장 배경

동적 계획법 등장 배경은 피보나치 수열을 통해 알 수 있다.

제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의된다. 제0항은 생략되기도 한다.

 

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

프로그래밍에서 피보나치 수열은 보통 재귀함수를 통해 표현한다.

아래는 피보나치 수열을 이용한 N번째 수를 구하는 함수이다.

fibo(7)은 어떻게 실행될까?

출처 : https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

 

fibo(4)의 연산이 두 번, fibo(3)의 연산이 세 번 중복되는 걸 볼 수 있다.

따라서 연산이 반복되는 결점을 보완하기 위해 동적 계획법이 등장했는데, 이는 처음 진행되는 연산은 기록해 두고 이미 진행했던 연산은 다시 연산하는 것이 아니라 기록되어 있는 값을 가져오는 것이다.

 

3. 동적 계획법의 조건

 

1) 부분 반복 문제

 - 위 설명과 같이 특정 부분이 반복되는 문제를 야기한다.

 - 따라서 기록되어 있는 값을 가져오도록 문제해결 (위 참고)

2) 최적 부분 구조

 - 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다.

 - fib(n)이 최적의 답이 되려면 작은 부분 문제인 fib(n-1)과 fib(n-2)가 최적의 답이 되어야 한다.

 

ex)

• fib(7)에서 구한 fib(4)
• fib(6)에서 구한 fib(4)
• fib(5)에서 구한 fib(4)
• fib(4)에서 구한 fib(4)

이 fib(4)의 값들이 항상 같은 값인 것이다.

그렇다면 fib(4)를 반복해서 연산하는 것은 의미가 없다.

 

이 두가지 문제를 해결하기 위해 메모이제이션이라는 동적 프로그래밍 개념이 도입하게 되었다.

 

4. 메모이제이션(Memoization)

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
- wikipedia

앞에서 알아본 피보나치 수열의 재귀함수를 메모이제이션을 적용하면 다음과 같다.

위 처럼 구하고자 하는 숫자의 크기 만큼 배열을 생성하고 계산한 값을 저장하고 

저장된 값일 경우 배열의 값을 리턴하는 방식으로 구현하면 중복되던 연산 과정을 줄 일 수 있다.

 

* 저장해두는 메모리(배열)을 캐시라고 부름

 

5. 동적 계획법 접근 방법

1)Top-Down

- 위에서 아래로 접근하는 방법, 재귀 호출 (피보나치 수 구하는 방식)

4번 사진과 동일

2)Bottom-Up

- 아래에서 위로 접근하는 방법, for문을 이용하여 푼다.

6. 동적 계획법 활용 방법

1) 문제에서 요구하는 답을 문장으로 표현한다.

2) 변수 개수 만큼 캐시 배열을 생성한다.

3) 문제를 부분 문제로 나누고 함수로 표현한다.

4) Top-Down: 재귀함수, Bottom-Up: for문을 사용하여 문제 해결

 

- 동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식이라 탐욕 알고리즘(그리디 알고리즘)과 이점을 잘 비교하여 문제에 적용해야한다.

 

탐욕알고리즘?

> 모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 구하는 알고리즘

 

* 동적 계획법 ) 항상 최적의 해를 도출 / 시간이 오래걸림

* 탐욕 알고리즘 ) 항상 최적의 해가 아닐 수 있음 / 시간이 짧게걸림