# upper bound
[C] 백준 10816 숫자 카드 2
링크 https://www.acmicpc.net/problem/10816 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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보다 작거나 같다. 출력 첫째 줄에 입력으로 주어
[알고리즘] lower bound & upper bound
1. lower bound & upper bound 이진 탐색이 정렬된 데이터에서 찾고자 하는 target data가 있는지 검색하는 알고리즘이라면, lower bound와 upper bound는 target data의 하한선 위치와 상한선 위치를 찾을 수 있는 알고리즘이다. 이진 탐색을 기반으로 동작하기 때문에 시간 복잡도는 O(logN)이며 정렬된 데이터에서 사용할 수 있는 기법이다. 2. 그림으로 이해하기 > lower bound : target data와 같거나 큰 데이터가 처음 나온 위치를 반환 (하한선) > upper bound : target data보다 큰 데이터가 처음 나온 위치를 반환 (상한선) 
이분 탐색
이분 탐색 오름차순으로 정렬된 정수 리스트에서 원하는 데이터를 찾는 알고리즘으로 한 번 검색할 때마다 검색 범위를 반으로 줄여가며 검색한다. 찾고자 하는 값 : ans 검색 범위의 왼쪽 끝 : left 검색 범위의 오른쪽 끝 : right 검색 범위의 중간값 : mid **알고리즘의 작동 방식은 아래와 같다. ** **검색 범위가 없다면 검색 값 없음 리턴 mid == ans이면 mid 리턴 mid ans이면 뒤쪽 절반에서 다시 탐색** 보통은 성능 문제때문에 재귀적으로 구현하지 않고 반복문으로 구현한다. 이분 탐색 구현 코드 Lower Bound와 Upper Bound 이분 탐색은 정확하게 찾는 값이 없으면 값이 없다고 리턴한다. 하지만 특정 값을 정렬된 배열의 어느 위치에 넣어야 하는지와 같은 기능을 수행하기는 어렵다. 원하는 값을 찾지 못했어도 가장 근접한 값을 리턴해주는 것이
[Java] Binary Search(이진탐색) 사용법, 예제
✨ Binary Search란? Binary Search, 이진탐색, 이분탐색 이라고 불리는 탐색 알고리즘의 종류이며, 순차적탐색을 이용했을 때, 성능이 나오지 않을 경우 사용할 수 있습니다. 이진/이분 이라는 뜻처럼 mid값을 중심으로 왼쪽/오른쪽 어디에 값이 있는지를 판단하며, 탐색범위를 1/2로 줄여나가며 찾는 방법입니다. 쉽게 예를 들면, up&down 게임과 같은 논리인데요, 1~100 중에 내가 생각한 숫자를 맞혀봐! 했을 때 1부터 100까지 하나씩 부르는 것보다 50 -> down, 25 -> up 이런식으로 찾는게 더 빠르다는 방식입니다. 하지만 이 방식이 무조건적으로 빠르다기보다는 모수가 많을 때, 더 효율적이겠죠? 구현 방식에는 크게 2가지로 특정값이 있는지만을 찾는 방식이 있고, upper bound, lower bound를 통해 범위를 찾는 방법이 있습니다. Binary Searc
알고리즘 - 이진 탐색
이진 탐색 영어로는 binarySearch라고 한다. 이 알고리즘은 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 여기서 핵심이 되는 말은 "정렬"이다. 이진 탐색이 이뤄지기 위한 조건이 바로 저 정렬되어 있다는 것이다. 이진 탐색 방식 알고리즘의 방식은 다음과 같다. 우선 정렬되어 있는 데이터 배열이 있다. 일단 오름차순이라고 가정하자. 우리의 목표는 값 k를 찾는 것이다. 이 이진 탐색 방식을 아래 순서로 설명한다. 배열에서 중앙에 위치하는 임의의 값을 확인하고 k와 비교한다. 값이 k보다 작다면 k는 해당 값보다 배열의 index 상 우측에 존재한다. 따라서 k 다음 값부터 마지막까지의 배열에 1번을 반복한다. 값이 k보다 크다면 반대로 k보다 작은 값들의
[Algorithm] Binary Search, Lower Bound, Upper Bound
개요 정렬된 자료를 절반씩 나눠가며 원소k의 위치를 찾는 탐색 알고리즘이다. 그리디 방법으로 탐색을 진행하면 O(N)이 걸릴것을 O(log N)에 마칠 수 있기때문에, 이후에 다른 알고리즘등에서 재사용이 많이되는 기본 탐색 알고리즘이다. 작동원리 (정렬된 연속된 자료가 필요하다.) 먼저 탐색범위를 설정한다. 왼쪽끝 인덱스를 left, 오른쪽 끝인덱스를 right로 두고, 두 인덱스의 중간인덱스에 해당하는 원소가 찾는 원소 k와 같은지, 작은지, 큰지에 따라 탐색 bound가 절반으로 나뉘게 된다. arr = {1, 3, 5, 7, 9, 11, 13}인 자료와, 찾는원소 k=5가 있다고 하면 아래와 같이 표시된다. arr[mid] == k ? : arr[mid] > k 이므로 이어서 탐색을 진행한다.
백준_7795 (먹을 것인가 먹힐 것인가_실버3_이진탐색_bisect 라이브러리_lower bound(python cpp)_매우 중요)
이진탐색 핵심 이진탐색 적용해야되는 문제 데이터 범위가 10,000,000을 넘어가는 경우(천만 이상 초대량의 탐색 필요 시) 이진탐색 문제는 크게 두 가지 유형이 있음 이진탐색을 해서 정해지지 않은 중앙값을 찾아내서 그 값에 따라 start end 조정 아래 문제처럼 bitsect라이브러리로 lower bound 사용해 특정 값 찾는 문제 링크 : https://www.acmicpc.net/problem/7795 
BOJ - 10816 숫자 카드 2
10816 숫자 카드 2 : https://www.acmicpc.net/problem/10816 Problem Solve 이전에 풀었던 문제 에서는 배열에 target의 존재 여부를 확인한 문제였다면. 이번 문제는 배열에 존재 여부가 아닌 존재하는 개수를 구하는 문제이다. 이진 탐색과 비슷하지만 조금 변형된 방법인 Upper Bound와 Lower Bound를 사용한다. Lower Bound는 배열에 존재하는 target에서 최초의 값을 반환하고 Upper Bound는 배열에 존재하는 target보다 다음으로 큰 최초의 값을 반환하는 것이
[백준]1654_랜선자르기.Kotlin
문제 문제로 이동하기 핵심 로직 이분 탐색으로 인덱스가 아닌 실제 값을 찾기 이분 탐색 중 Upper bound 를 활용하기 코드 풀이 랜선 자르기의 핵심은 여러 값들이 주어졌을 때, 문제의 조건을 만족하는 최댓값을 구하는 것이다. 비교를 해야할 여러 값들이 존재하고, 그 값들과 특정 조건이 만족하는 상황을 구하는 것인데 그림으로 표현하자면 다음과 같다. 
이진 탐색 & 매개 변수 탐색
https://annajeong.github.io/algorithm/parametric/ https://movefast.tistory.com/311 https://www.youtube.com/watch?v=F6lKjRDlOpk https://hee96-story.tistory.com/80 이진 탐색 >정렬된 배열에서만 사용할 수 있다 배열 내부의 데이터가 정렬되어 있어야 사용 가능한 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 변수 3개 = 시작점, 끝잠, 중간점 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는다. > 이진 탐색 동작 과정 1.단계 |0|2|4|6|8|10|12|14|16|18| |---|---|---|---|---|---|---|---|---|---| |시작점[0]| | | |중간점[4]| | | | |끝점[9]| 시작점
[Algorithm] Lower Bound & Upper Bound
Lower Bound & Upper Bound 하한선 알고리즘, 배열에서 특정한 값을 찾는 이 알고리즘은 이분 탐색(Binary Search)을 응용한 알고리즘으로, 정렬되어있는 배열에서 target이상의 값이 처음 나오는 위치를 찾는 알고리즘 이다. 반대되는 개념으로 Upper Bound(상한선)이 있으며, 이는 target이하의 값 중 가장 큰 값이 나오는 위치를 찾는다. 이진 탐색(Binary Search)류의 알고리즘은 target값이 나오지 않았을 때, 나오지 않을 것이라 판단되는 범위를 과감히 제외하고 탐색을 수행하기 때문에, 이진탐색 계열의 알고리즘을 수행할 때는 정렬이 필수로 되어있어야 한다. Lower Bound Upper Bound Binary Search
[TIL]Day 151
itertools chain 모듈을 사용하여 2차원 리스트를 일렬로 이어붙이기 list로 변환하지 않아도 max 같은 함수 사용이 가능하다. 프로그래머스 순위검색 효율성 떨어지는 코드 효율성 통과 코드 key point 0.딕셔너리에 미리 저장해둬야함 1.정렬 미리 해야함 2.이진탐색으로 찾아야함 upper bound 알고리즘 특정값 이상의 값이 나타나는 인덱스 반환
Lower Bound & Upper Bound
이진탐색(Binary Search) 자료구조의 종류 : 선형(Array & List..)과 비선형(Tree & Graph..) 이진탐색은 선형 구조의 탐색 방법 중 하나 분할 정복 방식으로 수행 > 순차 탐색의 경우 O(n) BUT 이분 탐색의 경우 O(logn) > > 정렬된 경우 효율적으로 탐색이 가능 > 이분 탐색 방법(1~100중 15 찾기) > 1) 1~100의 중간값인 50인지 물어본다. (작다) 2) 1~50의 중간값인 25인지 물어본다. (작다) 3) 1~25의 중간값인 12인지 물어본다. (크다) 4) 12~25의 중간값인 18인지 물어본다. (작다) 5) 12~18의 중간값인 15인지 물어본다. (o) Lower Bound(이상) 이진 탐색은 정확히 같은 값을 찾는 것에 비해 Lower Bound는 주어진 인자 값보다 작거나 큰 값이 처음으로 나올 때 Return 이진 탐색을 하며 인자 값과 같은 값이 나
[BOJ 7453] 합이 0인 네 정수 (Java)
BOJ 7453 합이 0인 네 정수 문제풀이 BOJ 2143 두 배열의 합의 아이디어를 그대로 사용하였다. A[]와 B[]를 합하는 모든 경우 AB[], C[]와 D[]를 합하는 모든 경우 CD[] -AB[]를 CD[]에서 찾기, 이진탐색(중복 값이 있으므로 upper, lower bound 사용) 구현코드
[BOJ 2143] 두 배열의 합 (Java)
BOJ 2143 두 배열의 합 문제풀이 주어진 A, B 배열에서 각각 합하여 나올 수 있는 모든 경우의 합을 리스트에 담는다. 첫 번째 리스트를 돌며 T - list[i] 가 두 번째 리스트에 있는지 확인한다. 어려운 문제였다... 모든 합의 경우를 가지고 있는 리스트 만들기 T = A + B 를 B = T - A 로 바꿔서 생각하기 upperbound, lowerbound 함수 구현코드