Jonyo Programming

LIS(Longest Increasing Subsequence) 알고리즘은 '가장 긴 증가하는 부분 수열' 알고리즘으로도 불린다. 주로 그리디 알고리즘이나 다이나믹 프로그래밍의 예시로 등장한다. LIS는 수열 내 증가하는 부분 수열 중 가장 긴 수열을 말한다. 예를들어 아래와 같은 수열이 존재할때 3 1 5 2 4 2 이때 가장 긴 증가하는 부분 수열은 {1,2,4}이며 길이는 3이다. 3 1 5 2 4 2 아래의 예시에서는 가장 긴 증가하는 부분 수열은 {10,20,30,50} 이며 길이는 4가 된다. 10 20 10 30 20 50 이제 이 알고리즘을 이용하는 문제를 해결해 보자. BOJ : 11053 가장 긴 증가하는 부분 수열 이 문제를 어떻게 풀어야할까? 이 문제는 동적계획법을 이용하여 O(N²..