Koo's.Co

bisect 라이브러리에 있는 bisect_left, bisect_right에 대해 공부하려 합니다. 1. bisect? - 정렬된 리스트에서 이진 탐색을 이용해 데이터를 찾는 메서드를 제공 - O(logN)의 시간 복잡도로 데이터를 찾을 수 있다 - bisect_left는 lower bound로, bisect_right는 upper_bound로 사용할 수 있다 2. lower bound와 upper bound bisect 라이브러리에서 제공하는 메서드는 이진 탐색과 완전히 일치하지는 않고 조금 차이점이 있다. 위에서 말한 것처럼 bisect_left는 lower bound 알고리즘을, bisect_right는 upper bound 알고리즘을 수행한다. - binary search: 찾고자 하는 값이 존..

1. 이진탐색? - 이진탐색은 정렬되어 있는 선형자료구조에서 사용할 수 있는 탐색 방법이다. - 정렬되지 않은 자료형의 경우 처음부터 차례대로 값을 비교해야하기 때문에 O(N)의 시간복잡도를 갖는다. - 반면 자료가 정렬되어 있는 경우 이진탐색을 통해 O(logN)의 시간복잡도로 값을 찾을 수 있다. - 이진탐색은 범위를 주면 해당 범위 중간값을 기준으로 찾고자 하는 값이 중간값보다 큰지 작은지를 판단하는 방법이다. - ex) 책에서 원하는 페이지 번호를 찾으려 할 때 일단 책을 펴고 찾고자 하는 페이지 번호가 더 작으면 앞부분을, 찾고자 하는 페이지 번호가 더 크면 뒷부분을 보는 것과 같다. 2. 이진탐색 알고리즘 - 찾고자 하는 값을 target이라 한다 - 리스트 nums가 주어지면 가장 작은 인덱..

정렬 리스트가 주어졌을 때, 해당 원소들을 키값에 따라 오름차순 또는 내림차순으로 배열하는 것을 말한다. 데이터를 정렬하는 이유는 탐색을 위해서이다. 정렬되지 않은 데이터에 대해 선형탐색(순차탐색)을 이용해 처음부터 비교해가며 값을 찾아야만 한다. 하지만 데이터가 정렬되어 있는 경우, 이진탐색을 이용한 빠른 탐색이 가능하다. 안정적 정렬(Stable Sort) 동일한 키값을 갖는 원소가 2개 이상 있을 때, 정렬 후에도 해당 원소들의 순서가 유지되는 것을 말한다 [1, 3, 4, 5, 3, 8, 11] 이라는 리스트가 주어졌을 때, 정렬 후에도 첫번째 3이 두번째 3보다 앞에 올 때 안정적 정렬이라 한다 제자리 정렬(In-place Sort) 입력받은 데이터 메모리 이외에 별도의 저장 공간을 상수개만 사..