programmer life guidance 101

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 71929 27658 18244 36.865% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {1..

Longest Increasing Subsequence) 최장 증가 부분 수열 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수 들을 선택해 부분수열을 만들 수 있는데, 이 때 만들어진 부분수열 중 오름차순으로 정렬 된 가장 긴 수열을 최장 증가 수열이라고 한다. 여기서의 부분 수열은 반드시 연속적이거나 유일하지 않아도 된다. 예를 들어 arr[ ] = {10, 20, 10, 30, 20, 50}의 수열이 있다고 할 때 여기서의 LIS는 {10, 20, 30, 50}이고 길이는 4일 것이다. 이제 이를 O(N2)과 O(nlogn)의 시간복잡도를 가지는 두 가지 방법을 알아보자. 1. DP 풀이 과정은 아래와 같다. i번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 arr[k]를 추가했을 때의 ..