DP(=다이나믹 프로그래밍,Dynamic Programming) 심화

재귀함수형태로 점화식이 생기는 문제에서 일대일함수임이 만족될때 각 함수의 파라미터를 키로 결과를 캐싱하는걸 dp라함
이때 캐싱하는 자료구조를 편의상 상태공간이라 부르는데 별 의미는 없고

 

 

동적계획법(Dynamic programming)은  자료구조에서 동적할당(Dynamic Allocation)과는 다르다.

알고리즘에서 사용되는 "다이나믹(Dynamic)"은 별다른 의미 없이 사용된 단어이다.

 

다이나믹 프로그래밍 문제인지 확인하려면 아래 조건을 만족하는지 확인하면 된다.

 

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

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

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

   : 동일한 작은 문제를 반복적으로 해결해야 한다.

 

 

예시) 피보나치 수열 : 하단 노드의 값을 합쳐서 풀어야함(1), 작은 문제를 중복적으로 풀어야함(2)

따라서, 피보나치 문제는 다이나믹 프로그래밍으로 풀 수 있다.

 

---

 

- 메모이제이션(Memoization) : 다이나믹 프로그래밍의 구현기법 중 하나. 한번 계산한 결과를 메모리 공간에 메모하는 방법이다. 값을 기록해놓는다(Caching, 캐싱).

 

 

탑다운 vs 보텀업

 

탑다운(하향식) : 구현과정에서 재귀함수를 이용. 작은문제들을 재귀적으로 호출하여 모두 호출되었을때 큰값의 결과가 나온다.

보텀업(상향식) : 아래서부터 해결해서, 결과값을 저장하여 아래서부터 위로 해결해나가는 과정. 다이나믹 프로그래밍의 전형적인 형태(결과 저장용 리스트(배열) = DP 테이블)

 

---

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

 

다이나믹 프로그래밍 : 한번 사용된 결과값을 반복적으로 호출한다.

분할정복 : 한번 분할이 이루어진 뒤에 해당 피벗을 다시 처리하는 부분문제는 호출하지 않는다.

분할정복

 

---

DP(Dynamic Programming)문제 해결 방법

 

다이나믹프로그래밍 유형임을 파악하는것이 중요.

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

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

3. 일반적 코테 수준에서는, 기본 유형의 다이나믹 문제(DP)가 출제되는 경우 多

=> DP 문제는 점화식 떠오르는데 오래 걸리므로, 코테에서는 좀 쉽게 나옴.

 

 

 

스킬1)

0번째부터 시작해서 i번째까지 오름차순으로 하나씩 포함해나가면서,

i번째값을 i-1 번째와 i-2번째 값을 이용하여 구하는 방식으로, 점화식을 구한다.

 

스킬2)

특정값으로 배열을 채우고 업데이트하는 방법

Java) Arrays.fill(배열, 채울값); 을 이용한다.

예시)

int[] array = new int[100];

Arrays.fill(array, 10001);

 

 

스킬3)

가장 긴 증가하는 부분수열(LIS알고리즘, Longest Increasing Subsequence)

: 가장 긴 증가하는 수열을 찾는 문제

array={4, 2, 5, 8, 4, 11, 15} 가 있을때 가장 긴 증가하는 부분수열은 {4, 5, 8, 11, 15}이다.

 

이러한 방식으로 구하는 방법은 

 

모든 0<=j<i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

 

이 방식으로 증가한다.

LIS 알고리즘

최종적으로 가장 긴 부분수열의 길이는 5이다.

그리고, 빼는 값은 N=7 에서 5를 빼서 7-5=2 이므로 두개를 빼면 최대 길이가 된다.

빠지는 값은 D[i] 값이 증가하다가 감소하는 구간을 측정하면 알 수 있다.