4Legs_Archives

문제 링크 : www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제에서 한 아이의 위치를 옮기는 것은 항상 맨 앞으로 보내거나, 맨 뒤로 보내는 것에 유의하자. 이렇게 위치를 옮기는 횟수를 최소화하려면, 최초 아이들의 순서에서 이미 번호 순으로 서 있는 아이들을 제외한 나머지를 옮기면 된다. 즉, 예제의 (3 7 5 2 6 1 4) 에서, 이미 3, 5, 6의 올바른 순서가 존재하므로 이들을 제외한 나머지 7, 2, 1, 4를 옮기면 1 ~ 7의 오름차순 순서를 만..

문제 링크 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 최장 증가 수열(LIS)에 대해 숙지하고 있다면 쉽게 해결할 수 있는 문제이다. 전체 수열의 크기가 1000으로 작기 때문에 O(N^2)의 시간복잡도를 갖는 DP를 사용할 수 있다. 수열의 한 수에 대해, 왼쪽 끝에서 그 수에서 끝나는 LIS와 오른쪽 끝에서 시작해 그 수에서 끝나는 LIS 길이의 합(-1)이 곧 바이토닉 수열의 길이가 된다. (이 때, 원래의 수는 그 바이토닉 부분 수열에서 가장 큰 값이 된다.) ..

최장 증가 수열 (LIS, Longest Increasing Subsequence) 최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다. 이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다. 아래의 예시 수열을 보자. 위 수열에서 최장 증가 수열을 찾으면 아래와 같다. 그림에서 붉은 칸으로 칠해진 부분 수열 (1, 2, 3, 6, 7, 9) 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분수열이다. 이제 주어진 수열에서 LIS의 길이를 구하는 두 가지 방법을 알아보자. 다이나믹 프로그래밍을 이용한 방법 : O(N^2) 이러한 최장 증가 수열을 찾는 가장 단순한 방법은 완전 탐색일 것이다. 하지만 수열에 존재하는 수의 개수가 k개일 때,..