lis 썸네일형 리스트형 [최장 증가 수열] LIS(Longest Increasing Subsequence) 이번 글에서는 DP중에서 특별한 케이스인 LIS에 대해 얘기해보자 합니다. LIS(Longest increasing Subsequence)는 가장 긴 증가하는 부분 수열 정도로 해석 가능합니다. 쉬운 이해를 위해서 예를 들어보겠습니다. 다음과 같은 수열이 존재한다고 해봅시다. 여기서 LIS를 찾는다면 다음과 같이 빨간 부분으로 색칠된 부분이 LIS가 됩니다. 눈치 빠르신 분들은 벌써 알아채셨을겁니다. LIS는 앞에서부터 뒤로 숫자를 선택하며 부분 수열을 구성해 나갈 때 증가하는 순서대로 숫자를 고르면서 고른 부분 수열의 길이가 최대 길이가 되도록 숫자를 선택하는 경우입니다. 보통 LIS를 구하는 문제의 답은 한 수열에서 주어지는 LIS의 길이가 답이됩니다. 즉, 그 수열에서 존재하는 모든 부분 증가 수열.. 더보기 BOJ)13711 LCS4 문제: icpc.me/13711 LCS의 크기를 구하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 LCS를 구할 수 있다. 하지만 LCS4 문제는 N이 10만이기 때문에 다른 방법을 생각해보아야 한다. 단순히 N이 10만에서 최장 공통 부분 수열을 구하라고 한다면 무척 어려운 문제가 되겠지만 다행히 조건이 더 주어진다. 1~N까지 정수는 두 수열 A,B에서 전부 한번 씩 주어진다는 것이다. 우리는 수열 A에서 입력을 받은 후 입력 받은 수의 인덱스로 A[x]의 들어온 순서를 삽입하는 방식으로 A수열을 정의 해준 뒤 A[B[i]]의 LIS를 구함으로서 최장 공통 부분 수열의 길이를 구할 수 있다. 이때 N이 10만이기 때문에 N^2 DP로 LIS를 구하는 방법은 안되고 NlogN 이분 탐색의 방법으로.. 더보기 이전 1 다음
