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

siino's 개발톡

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

https://www.acmicpc.net/problem/11053 최장 증가 부분 수열은 말 그대로 수열의 부분 수열 중에 가장 길이가 긴 것을 구하는 문제이다. 최장 증가 부분 수열을 푸는 방법은 크게 3가지로 분류된다. 1. 무식하게 풀기 - 완전탐색 (재귀) 2. dp 풀이 - 메모이제이션을 활용 3. 이분탐색을 활용한 풀이 - LIS(k): 길이가 k인 LIS 중 마지막 수가 최소인 수를 저장 ## 각각의 시간복잡도는 어떻게 될까? 1. 완전탐색 --------> O(2^N) 2. dp --------> O(N^2) 3. 이분탐색 --------> O(NlogN) 개념이 계속 헷갈려서 각각의 방법을 활용하여 직접 java 코드로 구현해보았다. 아래의 java 코드를 함께 보면서 알아보도록 하자...
알고리즘 2024. 1. 8. 17:35
이전 Prev 1 Next 다음