1818번: 책정리 문제 https://www.acmicpc.net/problem/1818 1818번: 책정리 동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터 www.acmicpc.net 풀이 책 번호를 오름차순으로 정렬하고자 하므로 가장 긴 이미 정렬되어 있는 책들은 놔두고 나머지 책들만 재배치를 하면 된다. 따라서 가장 긴 증가하는 부분 수열(LIS) 알고리즘을 사용해 LIS의 길이를 구하고, 책 수에서 LIS의 길이를 뺀 개수를 출력하면 된다. N의 범위는 2 × 10^5이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 시간초과가 나므로 시간복잡도가 O(NlogN..