블로그 이사 중입니다 >> gumgood.github.io

Longest Increasing Subsequence 본문

Problem Solving/분류없음

Longest Increasing Subsequence

gumgood 2017. 5. 27. 03:43

- LIS(Longest Increasing Subsequence) : 최대 부분 증가수열

- 수열에서 증가하는 순으로 고를 떄, 최대 길이를 갖는 수열을 말한다. (not unique)


설명이 굉장히 잘 되어있는 블로그가 있다. 여기도 괜찮다.


'LIS의 길이를 구하는 여러가지 방법이 있다. 시간 복잡도, 구현이 간단한지 등을 고려하여 문제에 맞는 알고리즘을 써야한다.


1. Dynamic Programming

  구현과 역추적이 쉽다.

  1차원 DP로 $(O^2)$에 해결할 수 있다. 


  C++11


2. Binary Search

  구현은 간단한 편이다.


  다음과 같은 수행과정을 따른다.

    ① vector 하나를 생성한다.

    ② 수열 arr를 처음부터 돌면서 vector의 마지막 원소보다

      - 큰 경우, vector에 push_back하고,

      - 작은 경우, vector에 증가수열을 유지할 수 있는 자리를 찾아 '교체'한다.

    ③ 최종적으로 만들어진 vector의 증가수열 길이가 LIS의 길이이다.

* 증가수열을 유지하는 자리를 찾는는 lower_bound()로 쉽게 해결할 수 있다. 


  해당 위치를 이분탐색으로 $O(logn)$ 만에 찾기 때문에 전체 시간복잡도는 $O(nlogn)$


  LIS가 어떤 수열인지 알고자 할 경우(역추적)

    따로 추가적인 연산을 해야한다. 만들어진 vector 내부 원소는 LIS와 관계가 없기 때문이다.

    LIS에 포함여부와 관계없이 vector 원소와 교체되기 때문이다.

    교체는 vector 길이에 영향을 주지 않기 때문에 LIS의 길이만 정확히 알 수 있다.


  LIS : C++11

  LIS + 역추적 : C++11


  역추적의 구현을 보면,

    원소가 1~n 사이로 들어오면 parent에 해당 원소를 바로 index로 쓸 수 있겠지만

    (ex, 999 998 1009) 이런식으로 들어오면 parent를 1000개 이상이나 잡을 수는 없다.

    따라서 parent[i]의 정의는 다음과 같이 정의한다.

      parent[i] := arr[i]로 끝나는 LIS에서, arr[i] 바로 앞 원소의 'index of arr'를 저장

    구현시, arr[i]로부터 index i도 알 수 있어야 하기 때문에 pair(arr[i],i)를 쓴다.

  결론은 소스가 지옥같다. 그래도 보고 이해할 수는 있다.


3. Segment Tree

  구현이 앞과 비하면 너무 귀찮다. 방법만 이해해야겠다.


  요약하자면 다음과 같다.

  각 arr[i]에 대해 DP[i] (i로 끝나는 LIS의 최대길이)를 max(DP[0]~DP[i-1)+1로 갱신하는

  $O(n)$과정을 segment Tree로 $O(logn)$에 해결한다. 이를 모든 i에 대해 반복하므로

  전체 시간복잡도는 $O(nlogn)$ 

  

'Problem Solving > 분류없음' 카테고리의 다른 글

Fenwick Tree, BIT  (0) 2017.05.27
Minimum Spanning Tree  (0) 2017.05.27
Longest Increasing Subsequence  (0) 2017.05.27
Segment Tree (구간 트리)  (0) 2017.05.27
Disjoint-set  (0) 2017.05.27
Diameter of tree  (0) 2017.05.27
Tag
,
0 Comments
댓글쓰기 폼