lds

[Algorithm] LIS, LDS (최장 증가 부분 수열, 최장 감소 부분 수열)

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 주어진 수열에서 요소들이 증가하는 순서대로 선택되는 가장 긴 부분 수열을 말한다. 즉, 주어진 수열에서 원래 순서를 유지하면서 순서대로 증가하는 숫자들을 선택하여 만들 수 있는 가 장 긴부분 수열을 찾는 문제이다. 예를 들어 수열 {3, 1, 5, 2, 4}가 주어졌을 때, 이 수열의 최장 증가 부분 수열은 {1, 2, 4}가 된다. 이 부분 수열은 원래 수열의 순서를 유지하면서 각 요소가 증가하는 순서대로 선택되었기 때문에 최장 증가 수열 부분이라고 할 수 있다. 최장 증가 부분 수열은 다이나믹 프로그래밍(DP)와 이분탐색을 이..