# Binary Search

ikkoun

이진 탐색 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법 ✅ 문제 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 손님이 왔을 때 요청한

ikkoun

이진 탐색찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요.단, 이 문제의 시간 복잡도 O(logN)으로 알고

chang626

레이스 K개의 위치는 N보다 작거나 같은 자연수이다.이분 탐색을 통해 구현한다.mid는 (0 + N) // 2로 구한다.이전 prev위치와 현재 i번째 위치에 저장되어 있는 값들의 차이를 구한다.만약 mid보다 크거나 같다면, 1을 추가하고 기준 값 업데이트심판을 다

choi-jaewon

[Algorithm] Binary Search

jnary

BFS와 DFS는 그래프를 탐색할 때 사용하는 알고리즘입니다. 이 포스팅에서 소개할 내용은 다음과 같습니다.1\. Binary Search가 무엇인가.2\. 코드로 이해하는 Binary Search.3\. 문제로 이해하는 Binary Search. 이진탐색, 이원탐색,

do_ng_iill

- 이진 탐색 : 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘. **찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교**해 원하는 데이터를 찾는 것이 이진 탐색 과정이다. - 시간복잡도 : **O(logN)**

wijoonwu

선형탐색 알고리즘 이진탐색 알고리즘의 개념에 대해 정리했습니다.

silver_star

https://www.acmicpc.net/problem/30790초 ~ (maxTime x m)초 범위에서 mid초에 대해, 심사 가능한 인원을 계산=> Init Call: binarySearch(0, maxTime \* m)maxTime x m: 최장 심사

kldaji

Problem linkSort number list in ascending order.Iterate 0, n - 1 with index i.Iterate 0, n - 1 with index j except (i == j) to avoid duplicate positio

yoongyum

contest 290 마지막 문제입니다.You are given a 0-indexed 2D integer array flowers, where flowersi = starti, endi means the ith flower will be in full bloom fro

silver_star

https://www.acmicpc.net/problem/11663완전 탐색하는 경우1개 선분에 대해 n개 좌표 확인: O(n)m개 선분에 대해 n개 좌표 확인: O(n x m)=> n, m 최대값 대입: 10^5 x 10^5 = 10^10 >> 1억 (시간

silver_star

https://www.acmicpc.net/problem/2512상한액 지정 액수에 따라, 지방 예산액이 정해짐=> 상한액을 1원 ~ m원까지 탐색완전 탐색할 경우, O(n x m) 으로 시간 초과 !!!=> 이진 탐색 수행Init Call: binarySea

yoongyum

남은 두 문제는 저는 풀지 못했습니다.다른 사람들의 코드를 보면서 분석해보겠습니다.Example 1(2,1) 좌표는 두개의 사각형에 포함되고 (1,4)좌표는 1개의 사각형에만 포함되어 2,1을 반환합니다.Example 2쉬워보이겠죠.제한조건을 보기전까진 brutefor

silver_star

https://www.acmicpc.net/problem/1789합 s 가 주어질 때, 자연수 개수 n이 최대가 되려면,합을 이루는 자연수 원소들의 값이 작은 순서로 구성되어야 함=> 1, 2, 3, 4, ... 와 같이 정렬된 배열 형태이진 탐색1 ~ end

kon6443

https://programmers.co.kr/learn/courses/30/lessons/43238binary search문제.탐색 전체를 하는데 가장 짧은시간 left = 가장 빠른 심사관 혼자 1명 검사탐색 전체를 하는데 가장 오랜시간 right = 가장

frombozztoang

Binary Search요소가 오름차순 혹은 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. p1 검색 범위의 맨 앞 인덱스pc 중앙 인덱스pr 마지막 인덱스1\. apc < key일 때,검색 범위를 apc+1 ~ apr로 좁힌다. p1의 값을 pc+1로 업데

chang626

피자 판매 반드시 연속된 조각들을 잘라서 판매한다.반복문을 통해 풀면 되는 문제이다.간격이 1씩 앞뒤로 차이가 나니!(1) 두 피자에서 한쪽 피자로만 줄 수 있는 경우의 수가 존재할 수 있으므로distA\[0] = distB\[0] = 1로 주었다.(2) 피자 한 판에

chang626

두 배열의 합 문제에서는 두 배열의 합을 더해서, T가 되는 모든 부 배열의 쌍의 개수를 구하는 프로그램을 작성하려고 하였다.이는 순차적으로 탐색을 하며, 완전 탐색을 해야하는 상황이다.배열의 합 : A\[i] + ... + A\[j] 그 사이의 합을 구하는 문제이다.

chang626

합이 0인 네 정수 이 문제는 무엇보다 시간을 잘 줄여야 한다.단순하게 반복문 4개를 돌릴 경우 O(4\*n)로 틀린 답이 된다.그러면 어떠한 방법이 있는가?a, b, c, d 총 합이 0이어야 한다.이는 a + b와 c + d의 총 합이 0이라는 의미이기도 하다.반복

chang626

부분수열의 합 2 N이 40개 이므로 모든 부분 수열을 다 구하려면 2^40번의 연산이 필요하다. (이는 1초안에 풀 수 없다.)수열의 길이가 40일 때, 왼쪽 오른쪽을 나눈다면(이분 탐색)왼쪽 : 20, 시간복잡도O(2^20)오른쪽 : 20, 시간복잡도O(2^20)이