LIS (1) 썸네일형 리스트형 백준 2352 반도체 설계 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net LIS 알고리즘 문제다. 밑의 알고리즘에서 이진탐색을 이용해서 idx 값을 구했기 때문에 탐색에 O(logN)이고 N개의 숫자에 대해 이 탐색을 실행하기 때문에 O(NlogN)이다. 이 문제는 LIS를 구할 때 "어떤 수열이 LIS인가?"를 묻지 않았기 때문에 그냥 개수만 찾았다. 그러면 arr에 들어있는 수열은 실제 LIS와 다를 확률이 아주아주 높다. 추적을 할 때는 ind.. 이전 1 다음