[ BOJ / 파이썬 ] 코테. 증가하는 부분 수열(LIS) 문제 시리즈

LIS 문제 푸는 알고리즘

1. O(N²)

1 부터 n 까지 차례대로,

  본인보다 인덱스 작은 애들 살피며

    본인 값보다 작은 값을 가진 애들 중

      가장 dp 값이 큰 애를 찾는다. 계속 갱신.

  그 큰 dp값으로 갱신된 상태 +1 (본인)

 

2. O(NlogN)

 

 

문제 샘플

1. 11053 가장 긴 증가하는 부분수열 ( 링크 ) ✅(O(N²) 풀이 )

2. 11055 가장 큰 증가 부분 수열 ( 링크 ) ✅(O(N²) 풀이 )