728x90 반응형 LIS1 최장 증가 부분 수열 최장 증가 부분 수열(LIS) 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다. O(n^2) 방법 for (int i = 0; i arr[j]) { if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; } } } } 매 순간마다 자기보다 작은 구간에 최댓값을 찾는 쿼리를 날려 최댓값 +1을 업데이트하는 방식으로 처리를 한다면, N번을 확인하.. 2019. 5. 5. 이전 1 다음 728x90 반응형