'longest increasing subsequence' 태그의 글 목록

[알고리즘] 최장 증가 부분 수열(LIS) 알고리즘

최장 증가 부분 수열(Longest Increasing Subsequence)이란? 원소개 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 간단히 말해, 가장 긴 증가하는 부분 수열이다. 예시 [6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열에서 최장 증가 부분 수열(LIS)은 [2, 5, 7, 8]이 된다. [2, 5, 7], [2, 4, 8] 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것은 [2, 5, 7, 8]이다. 최장 증가 부분 수열 알고리즘 풀이 방법 최장 증가 부분 수열의 길이를 구할 수 있는 풀이 방법은 크게 2가지가 있다. 동적계획법 (DP, Dyna..

Algorithm 2023.09.01

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Chadoll

longest increasing subsequence 1

티스토리툴바