새벽코딩

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