(알고리즘)Dynamic Programming - 동적 계획법

Dynamic Programming(동적 계획법)

: 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법

 

-> 간단하게 큰 문제를 작은 문제로 나누어 풀어가는 방법

 

 

 

[Dynamic Programming 방법]

동적 계획법은 나누어진 작은 문제들이 반복되는 경우, 이를 이용하여 문제를 푼다. (분할정복과는 차이점이 있다)

 

푼 작은 문제들은 어떠한 장소에 메모를 해 놓고, 큰 문제를 풀 때 반복되는 작은 문제가 나타날 경우에 메모 해 놓은 정보를 사용한다. (배열 dp[])

 

 

 

[Dynamic Programming 조건]

1. 큰 문제를 작은 문제로 나눌 수 있다

2. 중복되는 작은 문제들이 존제한다.

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

 

 

 

[Dynamic Programming 예시]

피보나치 수열

n번째 수열의 값을 구하는 경우

//값 초기화 조건 잘 따져 볼 것

dp[0] = 0

dp[1] = 1

dp[n] = dp[n-1] + dp[n-2]

 

대부분의 경우 간단한 식 한 두 개로 구현 가능

 

 

 

---

 

[Botton-up]

작은 문제부터 시작

-> 반복문을 사용한다

 

[Top-down]

큰 문제부터 시작

-> 재귀함수를 사용한다

 

---

tip) 작은 문제의 답을 찾아가며 규칙을 발견하여 풀면 보다 쉽게 풀 수 있다