백준 14003번 가장 긴 증가하는 부분 수열 5

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

  

문제풀이

사용한 알고리즘 : LIS

(0) 생각

 가장 긴 증가하는 부분 수열 (LIS) 를 구하는 문제입니다. 제가알기론 LIS 는 크게 DP를 이용한 풀이법과 segtree를 이용한 풀이법이 있습니다. (물론 더 좋은 풀이가 있을 수 있습니다.)
 저는 DP를 사용하여 문제를 해결하였습니다. ( 사실 lower_bound 만 쓴 것 같습니다. )
 제가 쓴 풀이가 이해하기 어려운 것 같습니다. 부족한 설명 죄송합니다... 쉽게 풀어 설명하기가 쉽지가 않네요... segtree를 이용한 풀이가 이해하기에는 더 쉬우니 다음에 올려놓겠습니다. (아마...)

 제가 작성한 최장 증가 수열의 비슷한 문제 링크를 올립니다.

 segtree를 통한 풀이도 작성하여 놓았습니다!

 백준 3745번 오름세

(1) 코드 9~12

 입력받은 수열을 i=0~>N-1 순으로 탐색 하면서 만들 수 있는 x길이의 LIS를 구성하는 성분들을 dp로 설정하였습니다.
 탐색을 하면서 arr[i] 를 포함하는 LIS 길이를 따로 배열을 만들어 저장해주었습니다. (탐색이 끝난 후 LIS 구성을 찾기위해)

(2) 코드 16~33

 i=0~>N-1 순으로 탐색하며 LIS를 구해주었습니다.
 i번째 탐색시 이전 1~i-1까지로 만든 LIS 의 배열의 끝값(dp로저장) 보다 arr[i]가 큰 경우, arr[i]를 끝값으로 붙여주었고, 그렇지 않은경우 해당 arr[i]가 들어갈 자리를 lower_bound로 탐색하여 찾아주었습니다.
 각 탐색마다 arr[i]를 끝값으로하는 LIS 길이를 따로 저장해주었습니다.

(3) 코드 41~48

 저장해 놓은 각 arr[i]를 끝값으로 하는 LIS 길이를 뒤에서부터 탐색하며 최종 LIS 구성을 찾아주었습니다.