최장 증가 수열

GUWONJOO·2021년 3월 25일
0

SSAFY TIL

목록 보기
9/18
  • 숫자가 나열된 형태의가장 긴 수열
  • 제한 조건 : 이 배열의 순서를 유지하면서 (순서 바꾸면 x) 크기가 점진적으로 커지는 가장 긴 부분 수열(부분집합 느낌)을 찾는 것

ex) 3,2,6 ->
3 32 x 326 x
2 36
6 26
->x 표시는 줄어들어서 안됨
따라서 이 예제의 답은 2 (가장 긴 길이가 2)
-> 부분집합(넣을까 말까)으로 풀어내면 7개의 예시 답을 얻을 수 있다.
-> 점진적인 성질을 갖추면서 길이가 가장 긴 수열을 찾자 !!

** LIS (Longest Increasing Subsequence)

  • 부분 수열의 길이가 긴 것부터 조사하는 것이 유리

  • 시간 복잡도 = O(2n) (2의 n승) -> n이 점진적으로 커지면 무한대가 되기 때문에 풀 수 없다.

  • D[n] : n원소를 끝에 세웠을 때 최장 길이

profile
SSAFY 5th

0개의 댓글