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

Dynamic Programming(동적 계획법) : 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 -> 간단하게 큰 문제를 작은 문제로 나누어 풀어가는 방법 [Dynamic Programming 방법] 동적 계획법은 나누어진 작은 문제들이 반복되는 경우, 이를 이용하여 문제를 푼다. (분할정복과는 차이점이 있다) 푼 작은 문제들은 어떠한 장소에 메모를 해 놓고, 큰 문제를 풀 때 반복되는 작은 문제가 나타날 경우에 메모 해 놓은 정보를 사용한다. (배열 dp[]) [Dynamic Programming 조건] 1. 큰 문제를 작은 문제로 나눌 수 있다 2. 중복되는 작은 문제들이 존제한다. 3. 같은 문제는 구할 때마다 정답이 같다. ..

2022.05.24