최장증가수열(LIS)
최장증가수열(LIS : Longest Incresing Subsequence) 수열이 나열되어있을 때, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제 ex) 3,2,6,4,5,1 라는 수열에서 최장증가 수열은 [2,4,5] 혹은 [3,4,5]이고, 길이는 3이다 이는 어떻게 구할까? 부분집합 부분집합을 통해 증가하면서 길이가 가장 긴 수열을 구할 수도 있지만, 부분집합은 시간복잡도가 2의 n승이기 때문에 수열이 길어질수록 시간적으로 부담이된다. https://java-is-happy-things.tistory.com/8?category=1266501 [Java] 부분집합 부분집합 : 한 집합에 포함될 수 있는 모든 집합들, 부분집합의 수는 2의n승이다. [입력] 3..
2022. 4. 6.
