LIS1 최장 증가 부분 수열, LIS 알고리즘 1. 가장 긴 증가하는 부분 수열, Logest Increasing Subsequence 증가부분수열이란, 주어진 수열의 일부 원소를 골라내서 만든 부분수열 중 모든 원소가 오름차순 부분 수열이다. 예를 들어 3 5 7 1 2 5 4 8 7 에서 3 5 7 8을 골라내면 이는 증가하는 부분 수열이다.1 2 7, 2 5 역시 마찬가지 이 중 그 길이가 가장 긴 증가 부분 수열을 최장 증가 부분 수열, LIS라고 한다. 위의 예시에서는 3 5 7 8 또는 1 2 4 8 이 LIS가 될 수 있다. 2. DP와 LIS LIS알고리즘 문제는 보통 주어진 수열에 대한 LIS의 길이를 구하는 것이다. 동적계획법, Dynamic Programming 알고리즘 문제의 예시로 쉽게 접할 수 있는 문제이므로 DP를 .. 2024. 5. 14. 이전 1 다음