[알고리즘 / Python] 가장 긴 증가하는 부분 수열 (LIS)
가장 긴 증가하는 부분 수열 알고리즘 이란, 왼쪽에서 오른쪽 방향으로 탐색할 때 오름차순으로 증가하는 부분 수열 중 가장 길이가 긴 부분 수열을 찾는 알고리즘이다. 0 1 2 3 4 5 6 10 40 20 50 30 40 60 위의 리스트에서 증가하는 부분 수열은 {10,40,50,60}, {10,20,50,60}, {10,20,30,40,60}, {40, 50, 60} 이 있다. 여기서 가장 긴 증가하는 부분 수열은 {10,20,30,40,60}이며, 부분 수열의 길이는 5가 된다. LIS 알고리즘은 두 가지 방법으로 구성될 수 있다. DP 활용 방법 이분탐색 활용 방법 1. LIS 알고리즘 (DP 활용) 시간복잡도: O(N**2) 1.1. DP 초기화 DP에는 부분 수열의 길이가 담기기 때문에 DP는..
Study/Algorithm
2023. 1. 16.