: o(n log n) (1) 썸네일형 리스트형 백준 14003 가장 긴 증가하는 부분 수열 5 이분탐색으로 LIS를 찾을 때 사용하는 방법은LIS 길이는 찾을 수 있지만 정확한 해당 수열은 아니다.정확한 수열을 찾기 위해서 아래처럼 추가적인 작업이 필요하다.a: 입력된 배열l: LIS 배열x: 입력데이터의 각 원소가 위 LIS 배열에 들어갈 때 인덱스를 저장해 두는 배열 x[i] = 0 : 입력데이터에서 i번째 있는 숫자는 LIS배열 맨 앞에 있다.m: x에서 찾은 최대값.r: 해당 x에서 m을 가지고 있는 위치부터 역순으로 m을 하나씩 줄여가며 가장 먼저 만나는 x의 인덱스를 배열로 구성r의 역순으로 정렬 후 각각의 r의 각 요소를 index로 하는 a값을 출력. 입력배열을 2 4 1 3 6 7 5 10 8 9 라고 할 때l과 x는 아래와 같이 변화한다. 2 처리시: l [2.. 이전 1 다음
