LIS 유형 문제

기본 LIS 문제

정렬되지 않은 수열에서 가장 긴 증가하는/가장 감소하는 부분 수열과 그러한 부분 수열의 길이를 구하는 유형의 문제가 있습니다.
일반적으로 이러한 LIS 유형의 문제는 수열의 길이(N)가 작을 경우는 2중 for문을 통해 해결이 가능합니다.
이와 관련된 문제 및 풀이는 다음과 같습니다.

 

소프티어 징검다리 문제

백준 긴 증가하는 부분 수열1 문제

 

백준 긴 증가하는 부분 수열1 문제 풀이

[백준] 11053. 가장 긴증가하는 부분 수열(Java)

 

최적화 LIS 문제

N의 최대 범위가 100만 이상으로 커질 경우 N^2 시간 복잡도로 인해 문제 해결이 불가한 상황이 발생합니다.
따라서 이때는 이분탐색을 적용하여 시간 복잡도를 N*logN으로 줄여 해결합니다.
이와 관련된 문제 및 풀이는 다음과 같습니다.

 

백준 긴 증가하는 부분 수열2 문제

백준 긴 증가하는 부분 수열2 문제 풀이

[백준] 가장 긴증가하는 부분 수열2 (Java)