LIS길이를 이분탐색으로 구해보자(python)
가장 긴 증가하는 부분수열(LIS)의 길이를 이분탐색을 이용해 구해보자 먼저 가장 긴 증가하는 부분 수열이 뭔지 이해해보자 수열: 숫자들의 나열 ex) [5,3,8,2] 부분수열: 수열안에서 몇몇 숫자들을 골라서 만든 새로운 수열 ex) [5,8,3,2] => [5,8,2] 따라서 수열 [10, 20, 10, 30, 20, 50]이 있을때 따라서 가장 긴 증가하는 부분 수열은 [10, 20, 10, 30, 20, 50]이고 길이는 4이다 이분탐색을 이용한 풀이 주어진 수열의 각 원소를 순회하면서 이분탐색을 적용해나간다 따라서 시간복잡도는 O(nlogn) 이된다 세부적인 이진탐색 과정은 아래와 같다 현재 원소를 이진 탐색을 통해 LIS 배열에 삽입할 위치를 찾는다 (LIS배열은 항상 정렬된 상태를 유지한다..
2023. 6. 6.
