가장 긴 증가하는 부분 수열 51 최장 증가 부분 수열 찾기 | 역추적 (Longest Increasing Subsequence Tracking) 2020/06/25 - [알고리즘] - 최장 증가 부분수열: LIS (Longest Increasing Sub-sequence) 지난 포스팅에서 LIS로 찾은 결과는 부분 수열의 최장 길이에 대한 정보만을 가지고 있을 뿐, 그 자체가 부분 수열이 될 수 없다는 점을 강조했다. LIS 역추적을 위해 pair 자료형 배열을 만들고 다음과 같이 정의하였다. pair LIS[MAX_SIZE] // first = 값, second = 인덱스 그리고 매번 arr배열을 탐색하면서 2가지 규칙으로 i번째 인덱스 앞에 올 인덱스 j (j LIS[_size-1].first) { lastidx = i; pre[i] = LIS[_size - 1].second; LIS[_size++] = { arr[i],i }; continu.. 2020. 6. 26. 이전 1 다음
