DP2. subsequence DP -- LIS와 LCS
연속이 필요없는 DP단일 배열에서 가장 긴 부분 수열 (subsequence) 의 길이를 찾는 문제 (LIS) 혹은 두 배열에서 가장 긴 공통 부분 수열의 길이를 찾는 문제 (LCS) 유형이다. 여기서 부분 수열은 subarray 랑은 다르게, 연속될 필요가 없다.LIS아래와 같은 array에서 값이 증가하는 가장 긴 부분 수열의 길이를 찾는 문제이다.nums = [10,9,2,5,3,7,101,18]LIS = [2,3,7,101]길이 = 4https://leetcode.com/problems/longest-increasing-subsequence/이를 어떻게 골라야 할까.DP우리가 구해야 하는 것은 LIS의 길이다. 따라서dp[i] = nums[i]를 마지막으로 하는 LIS 길이 로 정의한다. 그렇다면..
알고리즘/Dynamic Programming
2022. 5. 27. 07:21
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- cache
- bintrees
- dfs
- 공부법
- lru_cache
- connected components
- OJ
- 다이내믹 프로그래밍
- 동전문제
- 개발자 채용
- Kosaraju
- deque
- 합격
- 빅테크
- 프림
- 카카오
- nqueens
- Union-find
- 엔지니어
- graph
- 문자열
- 코테
- RTE
- 입출력
- coupon collectors' problem
- memoization
- iterable
- BFS
- python
- dp
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 |
글 보관함