가장긴 증가하는 부분순열(LIS)(N^2)

DP에서 많이 나오는 유형인 가장 긴 증가하는(감소하는) 부분순열에 대해서 정리해 보겠다.

​

1. 관련되어 백준에서 나오는 문제

 

11053번 가장 긴 증가하는 부분 수열

11054번 가장 긴 바이토닉 부분 수열

11055번 가장 큰 증가하는 부분 수열

11722번 가장 긴 감소하는 부분 수열

14002번 가장 긴 증가하는 부분 수열4 등이 알려드릴 방법으로 풀리는 대표적인 문제들이다.

​

12015번 가장 긴 증가하는 부분 수열2

12738번 가장 긴 증가하는 부분 수열3

14003번 가장 긴 증가하는 부분 수열5 의 경우, NlogN의 이분탐색으로 푸는 방법으로, 다른 알고리즘을 사용함.

이 문제들은 저한테는 어렵더라고요 ㅎㅎ... 나중에 알게되면 포스팅하겠습니당....

​

2. 푸는 기초적인 방법

​

우선 DP를 사용하는 O(N^2) 으로 푸는 방법임

핵심적인 아이디어는 앞에 것들을 다 확인해서 나보다 작은 수 들중 가장 긴 부분수열을 찾는다는 것이다.

​

ans[i] = i번째 원소를 마지막으로 하는 부분수열중 최장 길이

ans[i]=0~ i-1까지의 원소중에서 i번째 원소보다 값이 작은 것중 ans(길이)가 가장 긴 길이+1로 계산

​

3. 각 문제별 다른점

11053번: 위에 점화식 그대로 이용하면 됨

​

11054번: 현재 증가하고 있는가, 감소하고 있는가 두개의 상태의 ans를 각 i마다 만들고 점화식

​

11055번: ans의 값이 길이 대신 합이고, 점화식에 +1 대신 +(i번째 원소의 값)

​

11722번: 점화식에서 값이 작은것중 대신 값이 큰것중으로 바뀌면됨

​

14002번: 각 ans에 길이 값을 넣는것이 아니라 vector(queue도 가능)를 받으면됨

2차원 벡터를 이용하면 쉽게 구현가능 점화식은 +1이 아니라 vector에 원소 추가 vector길이를 이용하여 계산.

​

2차원 벡터 구현과 활용은 다음링크를 참조해주시면 감사하겠습니다.

C++ Vector 활용(구조체, 2차원 vector)

​

4. 11053번 정답 예시

​