Lis

LIS 알고리즘 - DP(동적계획법) LIS 알고리즘 - DP(동적계획법)LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 알고리즘은 주어진 배열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘이다.이 문제는 기본적으로 배열에서 연속적이지 않지만, 각 숫자가yarisong.tistory.com 저번에 이어 LIS알고리즘을 이용하여 가장 갈게 증가하는 부분 수열을 찾는 알고리즘 중 이분 탐색을 이용한 방법을 알아보자 1.LIS 알고리즘-이분탐색 이분탐색의 경우 시간 복잡도는 O(nlog⁡n)을 가진다. 이분탐색을 이용하는 경우에는 실제 LIS가 아닌 LIS의 길이를 구하는데 중점을 두는  알고리즘이다.이분탐색은 배열이 정렬되었다는 특징을 이용하여 탐색 범위를 절반씩 줄..