반응형
가장 긴 증가하는 부분 수열
-
BOJ) 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)알고리즘/백준 2020. 7. 27. 23:51
가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 어제 푼 가장 큰 증가하는 부분수열 (BIS)와 유사한 문제다. 다른 점이 있다면, 최대 값을 구하는 것이 아니라 최대 길이를 구하는 것이다. 그래서, Math.max를 통해 값을 증가 시켰던 것과 달리, Math.max를 통해 카운트를 증가시켜준다. 먼저, 자신만 존재하는 부분 수열에 대해서 dp[n]에 1을 저장한다. 이후, 탐색을 통해 자신보다 큰..