lis 알고리즘 동적계획법

LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 알고리즘은 주어진 배열에서 가장 길게 증가하는 부분 수열을 찾는 알고리즘이다.이 문제는 기본적으로 배열에서 연속적이지 않지만, 각 숫자가 이전의 숫자보다 커지는 수열을 찾는 문제이다.LIS 문제는 여러 방법으로 해결할 수 있지만, 대표적인 두 가지 방법은 동적 계획법(DP) 과 이분 탐색을 이용한 방법이다. 1. LIS 알고리즘 DP(동적계획법) 동적 계획법을 이용한 LIS 문제 해결은 O(n²) 시간 복잡도를 가진다. 다음과 같은 배열이 주어졌을 때 {50, 3, 20, 10, 2, 1} DP를 적용한 계산 과정을 살펴보자. 먼저 간단하게 알고리즘을 살펴보면 다음과 같다.LIS[i]: 인덱스 i까지의 수열에서 끝나는..