목록최장 증가 부분 수열 (1)

민규의 흔적

[알고리즘] LIS(최장 증가 부분 수열), 응용 문제 3가지

2024년 4월 16일 LIS (최장 증가 부분 수열) 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이란, 주어진 배열 내에 존재하는 여러 부분 수열 중 오름차순을 준수하며 가장 길게 나열되어 있는 부분 수열을 의미한다. 예를 들어, { 2, 3, 8, 6, 4, 5, 9, 1 } 라는 배열의 LIS는 { 2, 3, 4, 5, 9 } 이며 길이는 5 이다. 오름차순을 준수하는 부분 수열은 { 2, 3 }, { 2, 3, 5 }, { 2, 3, 6, 9 } 등 많지만, 가장 긴 부분 수열은 { 2, 3, 4, 5, 9 } 이다. LIS의 길이를 알아내는 방법은 대표적으로 완전 탐색법과 DP(다이나믹 프로그래밍), 이분 탐색이 존재한다. 이 중, 완전 탐색을 통해 모..
알고리즘 2024. 4. 16. 23:22
이전 Prev 1 Next 다음