최장 증가 부분 수열 (LIS) / 이분탐색

LIS (Lonest Increasing Subsequence)

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열 이라고 한다.

일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 방법은 DP를 이용한다.

이분탐색(이진탐색)

정렬이 되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 이진탐색은 시작점, 끝점, 중간점을 (인덱스) 이용하여 탐색 범위를 설정한다.
  (중간점이 소수점일 경우 소수점 이하는 제거한다)