가장 긴 증가하는 부분수열(LIS) 가장 긴 증가하는 부분 수열을 구하기 위해 아래와 같이 DP를 이용해서 풀 수 있지만, 이 경우 시간복잡도가 O(N^2)이기 때문에 N값이 매우 커지면 위험하다고 생각했다.//1. dpfor(int i=0; iA[j]) dp1[i] = Math.max(dp1[i],dp1[j]+1); }} 이분탐색, O(logN)이분탐색을 이용하면 DP를 이용했을 때 O(N^2)이었던 시간복잡도를 O(NlogN)으로 줄일 수 있다.public static void binarySearch(List arr, int target){ int left = 0; int right = arr.size()-1; while(left=target){ right = mid-1; }else{ ..
