새벽코딩

※https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ..

알고리즘 문제를 풀다보면 부분수열, 부분증가 수열등 여러 수열문제를 접할 수 있다. 그중 임의의 수열중 가장 긴 증가수열을 만들 수 있는 방법인 최장증가 부분 수열, LIS 알고리즘에 대해 기록한다. 1. 그림 예시로 보는 LIS 이해하기 다음과 같은 수열이 있다고 했을 때 우리는 다양한 방법으로 부분 증가 수열을 구할 수 있다. ex) 인덱스 0부터 시작하는 부분 증가 수열 ex) 인덱스 1부터 시작하는 부분 증가 수열 ex) 인덱스 2부터 시작하는 부분 증가 수열 ex) 인덱스 3부터 시작하는 부분 증가 수열 위처럼 여러 부분 증가 수열중 가장 긴 부분 증가 수열은 인덱스 0부터 시작하는 수열(length : 5)이 된다. 2. LIS 알고리즘 O(N²) 그렇다면 해당 알고리즘을 어떻게 코드로 구현할..