Longest Increasing Subsequence1 [C/C++] 백준 #1965 상자넣기(가장 긴 증가하는 부분수열) 이번 문제는 가장 긴 증가하는 부분수열을 찾는 문제입니다. 문제의 알고리즘 힌트에는 동적 프로그래밍을 이용하라고 되어 있지만, 동적 계획법을 이용하는 경우에는 \(O(N^2)\) 알고리즘으로 풀어야 합니다. 그에 비해 약간의 정책을 이용해서 풀면 \(O(N \log N)\) 알고리즘으로 풀 수 있습니다. 가장 긴 증가하는 부분수열이라는 것은, 부분수열중에 단순 증가하는 수열을 찾는 것입니다. 예를 들어서, 1 6 2 5 7 3 5 6 이란 수열이 있습니다. 부분수열은 순서를 지키면서, 이 수열에서 몇개의 수를 뽑아내는 것을 말합니다. 예를 들어서 1 6 2 5 도 이 수열의 부분수열이고, 1 2 7 6도 이 수열의 부분수열이 됩니다. 그런데, 증가하는 부분수열은 앞의 숫자보다 뒤의 숫자가 큰 경우를 의미.. 2022. 12. 10. 이전 1 다음
