[알고리즘] LIS(Longest Increasing Subsequence)
2021.03.03
LIS(Longest Increasing Subsequence_가장 긴 증가하는 부분 수열)이란? 백준의 다음 문제를 가지고 LIS를 정리해보자 ---> www.acmicpc.net/problem/11053 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 찾아야한다. 예를 들어, A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다. DP를 이용하여 풀 수 있다. DP 배열에는 해당 인덱스까지의 최대 길이를 저장한다. 먼저 첫 번째 인덱스에서는 당연히 자기 자신밖에 없기 때문에 최장 길이가 1이다. 두 번째 인덱스를 보면, 해당 값이 이전의 값보다 크기 때문에 이전 인덱스의 DP 배열의 ..