최장 증가 부분 수열 ( LIS )
Table of Contents 개요 O(n^2) 풀이 더 알아보기 : O(n log n) 풀이 1 더 알아보기 : O(n log n) 풀이 2 1. 개요 최장 증가 부분 수열 (longest increasing subsequence) 문제는 유명한 동적 계획법 활용 예시입니다. LIS 문제는 말 그대로 수열이 주어졌을 때, 수가 점점 증가하는 가장 긴 부분 수열을 찾는 문제입니다. 정확한 문제는 아래의 링크를 통해 확인할 수 있습니다. [BOJ 11053] 가장 긴 증가하는 부분 수열 2. O(n^2) 풀이 dp [ i ] = A [ i ] 를 마지막 원소로 하는 증가 부분 수열의 최장 길이 간단하게 위와 같이 dp 문제를 정의하면 해결할 수 있습니다. 이 dp의 정의는 A[1] ~ A[i] 수열의 L..
문제 풀이
2017. 11. 15. 22:15