# bisect

28개의 포스트

이진 탐색

이진 탐색❓ : 정렬되어 있는 리스트에서 탐색 범위(시작점, 끝점, 중간점)를 절반씩 좁혀가며 데이터를 탐색 vs. 순차 탐색: 리스트 안의 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법 시간 복잡도 O(log2N) : 단계마다 탐색 범위를 2로 나누는 것과 동일 코드 (1) 재귀 (2) 반복 파라메트릭 서치 (Parametric Search) : 최적화 문제를 결정 문제(예 / 아니오)로 바꾸어 해결하는 기법 ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 일반적으로 코딩 테스트에서 다음 문제는 이진 탐색을 이용하여 해결할 수 있음 bisect_left: 정렬된 순서를 유지하면서 배열 a를 x에 삽입할 가장 왼쪽 인덱스를 반환 bisect_right: 정렬된 순서를 유지하면서 배열 a를 x에 삽입할 가장 오쪽 인덱스를 반환

2023년 8월 21일
·
0개의 댓글
·
post-thumbnail

[Git] 오류가 발생한 커밋 찾기

코드를 실행하는데 예상치 못한 버그가 발생하고, 해당 버그가 오랜 버전 업데이트 과정에서 발견되지 않았었다면 어느 업데이트에서 발생한 오류인지 확인하기가 어려울 것입니다. git은 이에 대해 흥미로운 기능을 제공합니다. git bisect bisect 명령어를 통해 모든 버전을 다 체크하지 않고도 이진탐색으로 오류가 발생한 시점을 찾을 수 있습니다. 이진탐색 시작 탐색 시작 후 현재 커밋은 오류가 발생하는 상태라는것을 알려야 합니다. ![](http

2023년 8월 17일
·
0개의 댓글
·

백준 2631 파이썬

DP 문제 알고리즘 자신보다 앞에 작은 수의 개수를 테이블에 저장하여 가장 긴 증가하는 수열의 길이를 구할 수 있다. bisect 파이썬 라이브러리 이분탐색 라이브러리가 있는지 몰랐네?? ㅋㅋㅋㅋㅋ 배열이 정렬되어 있다는 가정 하에 사용 target의 숫자가 들어갈 수 있는 위치 중에서 가장 왼쪽 인덱스는 bisect_left 들어갈 수 있는 위치의 가장 오른쪽 인덱스는 bisect_right를 활용한다. 가장 긴 증가하는 수열 시간을 줄이기 위해 자기보다 작은 앞의 수를 찾을 때 이분탐색 사용 dp 테이블의 마지막 숫자보다 큰 수면 뒤에 붙여주고 작거나 같은 수라면 길이 변화가 없게 기존의 dp테이블 중에서 현재 target보다 같거나 큰 수의 위치를 찾아서 치환한다. dp의 길이를 통해 가

2023년 4월 24일
·
0개의 댓글
·
post-thumbnail

백준 10816번(Python) -숫자 카드 2, 리스트 요소 개수 세기

BOJ: Q10816 - 숫자 카드 2 [ 실버 4 ] 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 출력 첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각

2023년 4월 21일
·
0개의 댓글
·
post-thumbnail

0327 TIL

스터디 문제 풀기 ➡️ 수찾기 다른 풀이 bisect_left(list, x) 정렬된 list에서 x가 리스트에 있다면 x의 앞에 x를 삽입하는 꼴이 되기때문에 x의 인덱스를 반환해주고 x가 리스트에 없다면 x가 리스트의 정렬 순서상 삽입될 위치의 인덱스를 반환해준다 bisect_right(list, x) == bisect(list, x) x가 리스트에 있다면 마지막으로 나타난 x의 바로 뒤 인덱스를 반환해주고 x가 리스트에 없다면 삽입될 위치의 인덱스를 반환해준다 바이섹트 자체가 num이 nlist에 없어도 삽입될 위치를 반환해주는데 만약 a에 있는 것보다 큰 수를 삽입하게 되면 인덱스가 넘어가기때문에 i<len(nlist)가 필요하고 nlist에 있는 것보다 작은 수를 삽입하게 되면 인덱스를 원래 값의 인덱스들을 하나씩 밀기때문에 num=nlist[i]인지도 확인을 해줘야한다 django ORM 함수 Django O

2023년 3월 27일
·
0개의 댓글
·

이진 탐색 Bineary Search (예제)

예제 1) 떡볶이 떡 만들기 문제 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이 H를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기를 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm 이다, 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오. 조건 시간 제한: 2초, 메모리

2023년 2월 3일
·
0개의 댓글
·

이진 탐색 Bineary Search (개념)

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용해 탐색 범위 설정 시간 복잡도 $\rm{O(logN)}$을 보장하므로, 큰 수를 보면 가장 먼저 이진 탐색을 떠올릴 수 있어야 함 동작 예시 > 리스트: 0 2 4 6 8 10 12 14 16 18 찾으려는 데이터: 4 1) 시작, 끝, 중간점 설정 중간점은 소수점 이하 제거해서 사용 2) 찾고자 하는 값과 중간점의 값을 비교해서, 찾아야 하는 탐색 범위를 줄일 수 있음 ![](https://velog.velcdn.com/

2023년 2월 3일
·
0개의 댓글
·

표준 라이브러리

: itertools, heapq, bisect, collections, math 💡 파이썬 공식 문서 |라이브러리|설명 |--------|:-------------------- |내장 함수|기본 입출력 기능부터 정렬 기능(sorted())을 포함하고 있는 기본 내장 라이브러리 |itertools|반복되는 형태의 데이터 처리하는 기능을 제공하는 라이브러리순열과 조합 라이브러리 제공 |heapq| 우선순위 큐 구현에 사용 |bisect| 이진 탐색 기능 제공 |collections| deque, Counter 등의 자료구조 포함하는 라이브러리 |math|필수적인 수학적 기능 제공 내장 함수 Built-in functions import 명령어 없이 사용 가능 input(), print(), sum(), min(), max(), eval(), sorted(), s

2023년 1월 11일
·
0개의 댓글
·
post-thumbnail

이진 탐색

문제1) 입력) 출력) 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할수 있는 높이의 최댓값 출력 입력 예시) 4 6 19 15 10 17 출력 예시) 15 시간 제한: 2초 / 메모리 제한: 128MB 문제 풀이) 문제2) ![](https://velog.velcdn.com/images/wy929

2022년 12월 29일
·
0개의 댓글
·
post-thumbnail

백준 1920번 - 수 찾기 (파이썬) 문제 및 풀이

문제 https://www.acmicpc.net/problem/2667 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 풀이 DFS를 통해 단지 번호가 0인 것을 탐색합니다. 매 탐색마다 단지 번호를 1로 바꾸고 temp 변수를 통해 단지의 개수를 세어줍니다. 모든 단지를 탐색했으면, result 배열의 개수와 결과를 정렬하여 출력합니다. 코드 회고 알고리즘이 모듈로 구현되어 있어도 구현 방법을 정확이 알아놓자.

2022년 11월 22일
·
0개의 댓글
·

Bisect Library

bisect 는 이진 탐색을 쉽게 구현하게끔 해주는 함수입니다. 이진 탐색은 직접 코드로도 구현할 수 있지만, bisect 함수를 이용하여 구현 시간을 줄이고 편하게 사용할 수 있습니다. 예제 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 의 정렬된 배열이 있을 때, 현재 정렬된 상태를 유지하면서 n = 5 이라는 요소를 배열에 추가하고 싶다고 해봅시다. 어떤 인덱스에 넣어야하는지 계산하는 함수를 구해봅시다. 이분 탐색을 사용하지 않고 구현 배열이 오름차순으로 정렬된 점을 이용해서, mid를 집고, mid 인덱스의 값이 작으면 l(left) 을 mid +1 로 올려 다음 후보 값을 높여주고, 아니면 r(right)을 mid -1 로 내려 다음 후보 값을 낮춰주는 방식입니다. 절반씩 후보를 줄여가기에 O(logN) 이 성립합니다. 이 방법을 간단하게 해주는 것이 bisect 입니다!! bisect를 이용하여 구현 bisect_left(literab

2022년 10월 20일
·
0개의 댓글
·
post-thumbnail

리트코드_704 이진 탐색_Easy (이진탐색_뼈대문제_bisect 중요)

링크 : https://leetcode.com/problems/binary-search/ 알고리즘 및 방법 일단 기본적으로 바이너리서치는 "정렬되어있어야 함"을 전제로 푼다(안되어있다면 정렬시키고) 여러 방법이 있음 1) 라이브러리 사용 (중요) 핵심은 if nums[index] == target: <--- 이게맞으면 정답, 아니면 -1하면 된다 2) 기본 바이너리 서치 구현 솔루션 코드 bisect 라이브러리 사용 ![](https://velog.velcdn.com

2022년 9월 17일
·
0개의 댓글
·
post-thumbnail

[파이썬] bisect

biset 정렬된 리스트에서 특정 원소를 이진 탐색해주는 라이브러리 bisect_left(list, data) : 정렬된 리스트(list)에서, 정렬을 유지하며 data가 들어갈 가장 왼쪽 인덱스 리턴. >위 예시에서 bisect_left(a,3)은 2를 리턴. bisect_right(list, data) : 정렬된 리스트(list)에서, 정렬을 유지하며 data가 들어갈 가장 오른쪽 인덱스 리턴. > 위 예시에서 bisect_right(a,3)은 4를 리턴. 파이썬 코드 장점 원소들이 정렬된 리스트에서 특정 범위 내에 속하는 특정 값의 개수를 구할 때 효과적

2022년 9월 15일
·
0개의 댓글
·
post-thumbnail

이코테_이진탐색 기본 (부품 찾기_정렬된 배열에서 특정 수의 개수 구하기_bisect라이브러리)

1. 부품 찾기 메모 부품 n개 손님은 m개 종류의 부품을 구매하고싶음 가게 안에 해당 부품 m개가 모두 있는지 Yes or No 알고리즘 및 방법 내가 생각한 방법 1 간단한 방법 2 동빈나 해설 브루트포스로도 풀 수는 있겠지만, 부품 종류가 많거나, 손님이 찾는게 많을 경우 시간복잡도 오래걸릴 수 있따 브루트포스로 풀 경우 n을 전부 확인하면서 m에 해당하는 값들을 각각 찾는다 그럼 O(M * N)이 걸릴 것이다. (= O(N^2)이나 다름없음) 이진탐색으로 풀 경우 O(M * logN) 이 걸릴것이다 솔루션 코드 문제가 쉽고, 다른거 풀거 많으니 안풀겠음 동빈나 코드 2. 정렬된 배열에서 특정 수의 개수 구하기 메모 이미 오름차순 정렬된 배열에서 x가 등장하는 횟수 계산해라 단, 시간복잡도가 O(logN)으로 설계하지 않으면 시간초과를 받습니다.

2022년 9월 4일
·
0개의 댓글
·

bisect, bisect_left, bisect_right

bisect_left(arr, x):오름차순 정렬된 arr에 대하여 x 이상의 수 중 가장 왼쪽의 수의 인덱스를 리턴 bisect_right(arr, x):오름차순 정렬된 arr에 대하여 x보다 큰 수 중 가장 왼쪽의 수의 인덱스를 리턴 https://www.educative.io/answers/what-is-bisectbisectleft-in-python 이 링크에서 실험해볼 수 있다.

2022년 8월 18일
·
0개의 댓글
·
post-thumbnail

백준_7795 (먹을 것인가 먹힐 것인가_실버3_이진탐색_bisect 라이브러리_lower bound(python cpp)_매우 중요)

이진탐색 핵심 이진탐색 적용해야되는 문제 데이터 범위가 10,000,000을 넘어가는 경우(천만 이상 초대량의 탐색 필요 시) 이진탐색 문제는 크게 두 가지 유형이 있음 이진탐색을 해서 정해지지 않은 중앙값을 찾아내서 그 값에 따라 start end 조정 아래 문제처럼 bitsect라이브러리로 lower bound 사용해 특정 값 찾는 문제 링크 : https://www.acmicpc.net/problem/7795 ![](https://velog.velcdn.com/im

2022년 8월 14일
·
0개의 댓글
·
post-thumbnail

이진 탐색 핵심 설명 + bisect라이브러리(lowerbound) (중요)

용감한 파이썬-이진탐색 링크 : https://covenant.tistory.com/133 중요 포인트 데이터 범위가 10,000,000을 넘어가는 경우(천만 이상 초대량의 탐색 필요 시) 이진탐색은 기본적으로 "정렬"이 되어있는 상태! 그리고 Pivot을 사용한다! 주의사항 : 타겟을 제외한 모든 값은 index 넘버로 사용함을 주의하자!! (중요) 활용 방법은 다음과 같음 나무/랜선/떡 자르기처럼 정해지지 않은 임의의 중앙값을 찾아나가야할 경우 다음 그림과 같

2022년 6월 18일
·
0개의 댓글
·
post-thumbnail

bisect 모듈

안녕하세요. 오늘은 코딩테스트에서 종종 이용하게 되는 bisect 모듈에 대해서 알아보겠습니다. bisect 모듈이란 bisect 모듈이란 정렬된 배열에서 이진 탐색을 쉽게 구현할 수 있도록 도와주는 모듈입니다. 이진 탐색을 코드로 직접 구현하는 방법도 가능하지만, 정렬된 배열에서 크기를 비교하는 간단한 문제라면 bisect 모듈을 이용하여 더 쉽게 구현이 가능합니다. 이진 탐색을 구현한 모듈이기 때문에 시간복잡도는 O(logN)입니다. 주로 사용되는 함수는 다음과 같습니다. bisect_left bisect_left(array, item):정렬된 배열 array에서 item을 삽입할 수 있는 가장 왼쪽 인덱스를 반환합니다. 첫 번째 nums 배열에서 5가 들어갈 가장 왼쪽 위치는 4와 5 사이겠죠? 그렇다면 삽입될 위치의 인덱스는 5가 됩니다. 두 번째 nums 배열에서 5가 들어갈 가장 왼쪽 위치 역시 4와 맨

2022년 6월 2일
·
0개의 댓글
·
post-thumbnail

[2250] Count Number of Rectangles Containing Each Point | Medium | contest 290

남은 두 문제는 저는 풀지 못했습니다. 다른 사람들의 코드를 보면서 분석해보겠습니다. 🔎문제설명 Example 1 (2,1) 좌표는 두개의 사각형에 포함되고 (1,4)좌표는 1개의 사각형에만 포함되어 [2,1]을 반환합니다. Example 2 쉬워보이겠죠. 제한조건을 보기전까진 bruteforce로 풀면 25억번 루프를 돌아서 시간초과납니다. (경험담이구요.) > 제한사항 1 ≤ rectangles.length, points.length ≤ $$5 * 10^4$$ -

2022년 4월 25일
·
0개의 댓글
·
post-thumbnail

[Leetcode] 704. Binary Search

📄 Description Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity. 정렬된 nums를 입력받아 이진 검색으로 target에 해당되는 인덱스를 찾아라. Example 1: Example 2: 🔨 My Solution

2022년 3월 16일
·
0개의 댓글
·