백준11053: 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053 이 문제는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)에 대한 기본적인 문제입니다. 매우 중요한 알고리즘이므로 반드시 숙지해야 합니다. 1.

Problem Analysis 이 문제는 길이가 N인 수열 A에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제입니다. 이 문제의 제한조건은 다음과 같습니다.

수열의 길이 N은 1,000 이하의 자연수이다. 수열 A의 각 원소는 1,000 이하의 자연수이다.

시간제한 1초, 메모리제한 256MB 이 문제는 LIS 알고리즘을 알고 있으면 손쉽게 해결할 수 있습니다. LIS 문제의 핵심은 "어떻게 가장 긴 증가하는 부분 수열을 찾아낼 것인가"입니다.

이 방법은 순서 지정과 다이나믹 프로그래밍을 이용해서 해결할 수 있습니다. 즉, i번째 원소를 마지막 원소로 갖는 부분 수열에서 가장 긴 증가하는 부분 수열의 길이를 순차적으로 구하는 겁니...

요청 처리 중입니다...

백준11053: 가장 긴 증가하는 부분 수열

등록된 다른 글