Lis (1) 썸네일형 리스트형 [Algorithm] 최장 증가 부분 수열(LIS: Least Increasing Subsequence) 문제를 푸는 두 가지 알고리즘 이 글은 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제인 최장 증가 부분 수열 문제와 이를 푸는 알고리즘 두 가지에 대해 설명한다. 최장 증가 부분 수열 문제 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거해서 부분 수열을 만들 수 있다. 주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 문제를 최대 증가 부분 수열 찾기 문제(LIS: Least Increasing Subsequence)라고 부르며, 이는 매우 유명한 동적 계획법 알고리즘 문제 중 하나이다. 이 문제를 푸는 대표적인 알고리즘이 두 가지 존재한다. 알고리즘 답을 구하는 데에 필요한 배열 A, D를 정의하자. A[i], D[i]는 다음과 같다. A[i]: 수열의 i번째 수 D[i]: A[i]를 마지막 .. 이전 1 다음
