오늘 배운 내용
-
알고리즘 - DP
leetcode 300 Longest Increasing Subsequence
이 문제도 오래 고민하다가 결국 풀지 못했는데 DP를 사용해야 된다는 생각 자체를 떠올리지 못했다.
쉬운문제 였는데 알고리즘 문제를 2달 정도 쉬니까 아예 백지화 되버린거 같아서 개념부터 다시 정리를 하려고한다.
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;
}
}
이번 수의 최장수열은 앞의 수들 중에서 이번 수보다 작은 수의 최장수열중 가장 큰값에서 +1을 한 값이므로 DP를 사용한다.
알고리즘 - DP
알고리즘들에 관한 내용들을 한번씩 정리해 보려고 한다.
이번에 문제를 풀면서 DP를 제대로 생각하지 못했기 때문에 DP에 관한 내용을 정리했다.
DP는 문제를 분할해서 해결하는 분할정복의 일종으로 분할정복과 다른점은
작은 문제들의 결과가 반복해서 필요하고 이를 위해서 Memoization을 통해서 결과를 저장한다.
정리 : Algorithm - DP
