lis

문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.https://www.acmicpc.net/problem/12738      제한 사항      풀이문제를 요약하면, 주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 것이다.유명한 DP문제인 LIS를 구현하면 된다. 하지만, 해당 문제의 난도가 높게 평가된 이유는 아마 시간 초과를 해결해야 하기 때문이다.보통의 LIS는 $O(N^2)$의 시간복잡도를 갖는다.i번째 이전의 수중 i번째 수보다 더 작은 수가 갖고 있는 가장..

문제 설명KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.3 7 5 2 6 1 4아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.3 7 4..