#11053 (1) 썸네일형 리스트형 [Baekjoon]11053.가장 긴 증가하는 부분수열(DP) Baekjoon #11053. 가장 긴 증가하는 부분 수열http://www.acmicpc.net/problem/11053 이 문제는 Longest Increasing Subsequence(LIS)로 유명한 문제라고 한다. 그 동안 풀었던 문제와는 다른 유형인 것 같아서 아이디어가 떠오르지 않았는데 유튜브에서 영상을 보고 바로 이해가 되어 풀 수 있었다. 이 영상이 도움이 되었다. 영상에서 설명한 방법은 시간복잡도가 O(n^2) 이다. 그런데 n이 100,000 이상일때는 이 방법으로 풀 수 없다. 시간 복잡도 O(nlogn) 인 방법이 있는데 이번 포스팅에서는 먼저 O(n^2)인 방법으로 풀고 이후에 따로 O(nlogn) 방법을 공부하여 포스팅 해야겠다. 먼저 배열 d를 정의하면 d[n] : 수열 a에.. 이전 1 다음
