Dynamic Programming (동적 계획법)
Dynamic Programming 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 Memoization을 사용해서 해결한다.
DP는 Bottom-up, Top-Down두가지 방법으로 구현할 수 있다.
Memoization (메모이제이션)
동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써,
동일한 계산의 반복 수행을 제거하여 시간 복잡도를 줄인다.
이때 저장하는 메모리가 흔히 들어본 cache(캐시) 이다.
즉, DP는 Memoization을 통해 캐싱해서 공간복잡도를 활용해 시간복잡도를 줄이는 방법이다.
부분 문제 반복
동일한 문제를 여러 번 반복하여 해결하는 방식으로,
이를 활용해 큰 문제를 작은 부분 문제로 쪼개어 해결한다.
dp[i] = dp[i-1] + dp[i-2] 와 같은 형태가 모든 문제에서 성립한다.
ex ) 피보나치 수열
최적 부분 구조
작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있는 구조
dp[i] = dp[j] + ? 같은 형태로 조건을 만족하는 j까지의 최적의 답을 통해서 dp[i]의 값을 구한다.
즉, 부분 문제 반복에 어떤 조건이 추가된 형태라고 생각된다.
ex) 배낭 문제, 최장 수열 구하기
## Bottom-up (상향식)
작은 문제에서 시작하여 점점 큰 문제를 풀어나가는 방식으로 for문을 사용해서 구현 한다.
아래는 최장 수열 문제를 상향식으로 구현
public class Solution
{
static int maxLength = 0;
public int LengthOfLIS(int[] nums)
{
int[] dp = new int[nums.Length];
dp[0] = 1;
int maxLength = 1;
for (int i =0; i< nums.Length; i++)
{
int maxval = 0;
for(int j = 0; j < i; j++)
{
if (nums[i] > nums[j])
{
maxval = Math.Max(maxval, dp[j]);
// 0 부터 이번에 새로들어온 i 까지 i와 비교
// 만약 새로 들어온 i 가 j보다 크다면
// j까지의 최장수열에서 + 1된것이 이번 최장수열임
}
// 이번 최장수열은?
dp[i] = maxval + 1;
// 지금 까지의 최장수열은?
maxLength = Math.Max(maxLength, dp[i]);
}
}
return maxLength;
}
}
## Top-Down (하향식)
큰 문제에서 시작하여 문제를 부분 문제로 쪼개는 방법으로 재귀 호출을 사용해서 문제를 푸는 방법
최장 수열 문제는 가장 긴 수열을 구해야되서 하향식으로 구현하려니 문제가 생겼다.
최장 길이를 저장하는 부분에서 재귀함수를 마지막 인덱스를 기준으로만 호출하게 되면
모든 문제를 탐색할 수 없어서 제대로 최장 길이를 구할수 없었고
그래서 for문을 한번 더 사용해서 모든 문제를 탐색할 수 있도록 해주니 문제가 해결됬다.
public class Solution
{
int maxLength;
int[] dp;
public int LengthOfLIS(int[] nums)
{
maxLength = 1;
dp = new int[nums.Length];
dp[0] = 1;
//maxLength = Math.Max(maxLength,Recurse(nums, nums.Length));
for(int i = nums.Length -1; i>=0; i--)
{
maxLength = Math.Max(maxLength,Recurse(nums, i));
}
return maxLength;
}
public int Recurse(int[] nums, int index)
{
if(dp[index] == 0)
{
int maxval = 0;
for (int i = index-1; i >= 0; i--)
{
if (nums[index] > nums[i])
{
maxval = Math.Max(maxval, Recurse(nums, i));
}
}
dp[index] = maxval + 1;
}
return dp[index];
}
}