binary search

최장 증가 부분 수열 (LIS)

개념 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로 몇 개의 숫자들을 뽑아서 부분수열을 만들 수 있다. 이렇게 만들 수 있는 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어 [5, 2, 1, 4, 3, 5] 라는 수열이 있다고 가정해보자. 해당 수열에서 최장 증가 부분 수열에 해당하는 수열은 무엇일까? 세번째에 있는 숫자 1을 꺼낸다. 다섯번째에 있는 숫자 3을 꺼낸다. 여섯번째에 있는 숫자 5를 꺼낸다. 이렇게 만들어진 수열 [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이 된다. 구할 수 있는 방법에는 크게 2가지가 있고 시간 복잡도에서..

[C++] 이분 탐색 (Binary Search)

이분 탐색(Binary search)이란? - 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘. - 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. - 재귀적인 방법, 반복문, STL를 이용하여 이분 탐색(Binary Search)을 실행할 수 있다. - Time Complexity : O(log N) 변수 설명 1. int low & int high 검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수. left는 시작점을, right를 끝점의 인덱스를 가리킨다. // nums에 수들이 들어가있다고 가정 vector nums; int low = 0; // 초기 세팅: 제일 앞 인덱스 int h..

[C] 이진 탐색 (Binary Search) 알고리즘 개념과 예제

이진 탐색 이진 탐색은 오름차순으로 정렬되어있는 데이터에서 원하는 값(타겟 넘버)의 위치를 찾아내는 알고리즘이다. 여기서 이진(Binary)는 우리가 알고있는 그 이진 코드 (0101001...) 가 아니라 데이터를 반(2개)으로 나누어서 비교하고 찾는 방식이여서 이진 탐색이라고 한다. 이진 탐색의 알고리즘 진행방식은 아래와 같다. 정렬되어있는 데이터의 중간 값을 임의의 값 X로 정함 타겟 넘버의 값과 X를 비교 타겟 넘버의 값이 X보다 크다면, 타겟 넘버는 데이터에서 X보다 우측에 위치해 있으니 반으로 나눈 데이터의 우측에서 1번 과정부터 다시 시작 타겟 넘버의 값이 X보다 작다면, 타겟 넘버는 데이터에서 X보다 좌측에 위치해 있으니 반으로 나눈 데이터의 좌측에서 1번 과정부터 다시 시작 이진 탐색 예..