[BOJ] DP 11053 가장 긴 증가하는 부분수열 C++
11053번 가장 긴 증가하는 부분 수열 📝문제링크 : www.acmicpc.net/problem/11053 지금까지 풀었던 DP 중 제일 어려웠다. 정답코드를 보고도 접근 방법이 잘 연상되지 않았다. solved.ac 등급이 silver2 던데, silver1 문제보다 어려운 거 같은데...🤔 가장 긴 증가하는 부분 수열은 LIS 라고도 불리는데, 유명한 개념이니까 확실히 알고 넘어가는게 좋을 것 같다. 접근 과정 1. DP니까 당연하게도(?) memoization으로 접근해봐야지. $dp[i]$ : arr[i]이 배열의 마지막 원소일 때, 가능한 가장 긴 증가하는 부분 수열의 길이가 저장된다. dp[i] 에 저장될 값은, arr[i - 1] 까지의 가장 긴 증가하는 부분 수열에 arr[i] 값을 붙일..
알고리즘/Problem Solving
2020. 12. 28.
