이분 탐색

LIS(최장 증가 부분 수열)이란?LIS란 말 그대로 어떤 수열의 부분 수열 중, 가장 긴 증가하는 부분 수열을 의미한다.예를 들어, {10, 20, 10, 30, 20, 50} 인 수열의 LIS는 {10, 20, 30, 50} 이고, 길이는 4이다. 어떻게 구할까?1. 완전 탐색 - $O(2^N)$모든 부분 수열을 구한 후, 증가하는 부분 수열 중 가장 긴 수열을 구하는 방법이다.말 그래도 모든 부분 수열을 구해야 하므로, $O(2^N)$의 시간이 걸린다. 2. 다이나믹 프로그래밍 - $O(N^2)$$A_i$을 마지막으로 가지는 가장 긴 증가하는 부분 수열의 길이를 $DP[i]$라고 해보자.각 원소별로, 해당 원소($i$)보다 앞선 원소들($j$)을 탐색한다.$A_i > A_j$인 원소들 중 $DP[j..

이분 탐색(Binary Search)이분 탐색이란 정렬된 배열에서 범위를 반씩 줄여나가면서 원하는 값을 탐색하는 방법으로, 분할 정복(Divide and Conquer)을 사용하는 대표적인 알고리즘 중 하나이다.이분 탐색이라는 단어를 모르더라도, 업-다운 게임을 해봤다면 한 번쯤 써본적이 있는 기법일 것이다.  위 그림은 파란색 표시된 값 9를 이분 탐색으로 찾는 과정이다.각 상황에서의 중앙값과 찾고자 하는 값을 비교하며 범위를 줄여나간다. 구현해보기(코드)두 변수 $low$와 $high$를 이용해 탐색 범위를 관리할 것이다.초기 범위를 0 ~ (배열의 길이 - 1)로 두고 범위를 점점 좁혀나가면 된다.def binarySearch(arr, target): low, high = 0, len(arr)..