All posts by:Matthew

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/14003 O(nlogn) 시간 복잡도로 LIS를 찾는 데 사용할 수 있는 알고리즘이 있습니다. 이 알고리즘은 이진 탐색을 사용하여 가장 긴 증가하는 부분 수열의 길이를 찾습니다. 이 알고리즘은 먼저 크기 n + 1의 벡터 dp를 생성합니다. 여기서 dp[i]는 인덱스 i에서 ...

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/14002 가장 긴 증가하는 부분 수열(LIS)은 수열의 요소를 포함하는 증가하는 수열 중 가장 긴 수열입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}의 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50}이고 길이는 ...