0. 최장 증가 부분 수열 LIS최장 증가 부분 수열 LIS어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있을 때, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출하는 문제를 의미한다.ex) 3, 2, 6, 4, 5, 1의 배열의 LIS 해 중 하나는 2, 4, 5이다.이 문제를 부분집합으로 접근하면 시간 복잡도가 O(2^n)이므로, DP나 이진 검색을 활용하여 접근하는 것이 효율적이다.1. DP를 활용한 접근각 원소까지의 LIS 길이를 저장하는 배열인 LIS라고 할 때, LIS(i)를 이전 단계들과의 관계로 표현해보자.Case 1: LIS(i)가 a_i를 부분 수열의 마지막으로 포함하지 않는다면 → LIS(i) = LIS(i - 1)Case 2: LIS(i)가 a_i를 부분 수..

0. 이진 탐색(Binary Search)이진 탐색은 타겟(원하는 값)을 찾을 때까지 이진 탐색을 반복 수행하며 검색 범위를 반으로 줄여가면서 순차 탐색보다 빠르게 검색을 수행하는 알고리즘이다.단, 이진 탐색을 하기 위해서는 자료가 정렬된 상태여야 하는 제약이 존재한다. 분할 정복을 기반으로 하는 방식으로, 분할 정복을 알고 있다면 더욱 이해하기 쉽다.1. 이진 탐색의 로직자료의 중앙에 있는 원소를 고른다.중앙값(중앙 원소의 값)과 타겟을 비교한다.중앙값과 타겟이 일치하면 탐색을 끝낸다.타겟이 중앙값보다 작으면 자료의 왼쪽 반에 대해 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해 새로 검색을 수행한다.찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다아래 그림은 6을 찾는 이진 탐색의 그림이다...