lis (1) 썸네일형 리스트형 [Baekjoon]12015.가장 긴 증가하는 부분수열2 Baekjoon #12015. 가장 긴 증가하는 부분 수열2 http://www.acmicpc.net/problem/12015 11053과 같은 문제이지만 N제한이 더 커서 O(N^2)의 방법으로 풀면 시간 초과가 난다. 따라서 O(NlogN) 방법으로 풀어야 한다. 이진 탐색을 활용한 lower bound 알고리즘을 사용했다. Lower Bound : 배열에서 찾고자 하는 값 k가 있을때 k보다 크거나 같은 값의 첫번째 인덱스를 리턴. 예) 배열 {1, 1, 3, 5, 6} 에서 k=1 일때 Lower Bound = 2(1보다 크거나 같은 값은 3이므로 3의 인덱스인 2를 리턴) 먼저 LIS를 저장할 빈 배열을 하나 생성하여 이를 갱신해나가면서 LIS를 구한다. 입력된 배열 a = {10, 20, 10.. 이전 1 다음
