# lowerbound

18개의 포스트

JavaScript-lowerBound()와 upperBound()를 이용해 특정 범위에 속하는 원소의 개수 구하기

lowerBound()와 upperBound() 정렬된 배열에서 값이 특정 범위에 해당하는 원소의 개수를 계산할 때에 사용 lowerBound(arr,x):정렬된 순서를 유지하면서 배열 arr에 x를 넣은 가장 왼쪽 인덱스를 반환 upperBound(arr,x):정렬된 순서를 유지하면서 배열 arr에 x를 넣은 가장 오른쪽 인덱스를 반환 countByRange():위의 두 함수를 사용하여 정렬된 배열에서 값이 특정 범위에 속하는 원소의 개수를 계산할 수 있음

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

백준 10816 - 숫자 카드2 자바로 구현

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

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

선형 검색과 이진 검색

개요 리스트에서 검색을 하는 방법에는 2가지가 있다. 선형 검색과 이진 검색이 그것이다. 선형 검색 선형 검색은 리스트 전체를 하나씩 순회하면서 검색하는 방식이다. 선형 리스트와 연결 리스트 모두에서 사용할 수 있다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)이다. 이진 검색 이진 검색은 검색할 범위를 반으로 줄여가며 검색하는 방법이다. 이진 검색은 정렬된 선형 리스트에서 사용할 수 있다. 시간 복잡도는 O(logn) 공간 복잡도는 O(1) ![](https://velog.ve

2023년 2월 25일
·
0개의 댓글
·
post-thumbnail

[ 알고리즘 ] lower_bound, upper_bound

Lowerbound, upperbound 모두 이분탐색에서 파생된 것으로 역시 자료들이 정렬되어 있어야 합니다. > - Lower_bound : 원하는 값 target 이상의 값이 처음으로 나오는 위치를 찾는 알고리즘 > - Upper_bound : 원하는 값 target 을 초과하는 값이 처음으로 나오는 위치를 찾는 알고리즘 Upperbound의 값과, Lowerbound의 차로 target의 개수를 찾을 수 있습니다.

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

JavaScript 코딩테스트 - lower_bound, upper_bound

코딩 테스트 대비 저장용 포스트입니다. C++에는 algorithm 으로 해당 기능을 지원했는데 없어서 구현해보았다. BOJ 10816번: 숫자 카드 2 문제 upperbound - lowerbound로 그 수의 개수를 계산했다. (이 문제는 다른 방법이 더 쉽긴 하다.)

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

파이썬 bisect_right , bisect_left 를 Java로 구현한 것 [upper_bound , lower_bound , bound , bisect]

참고 블로그 : https://codingdog.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-bisectright-bisectleft-%EA%B0%81%EA%B0%81-upperbound-lowerbound%EC%97%90-%EB%8C%80%EC%9D%91%EB%90%9C%EB%8B%A4 > 참고 유튜브 및 Github : 나동빈 님 > 유튜브 : https://youtu.be/94RC-DsGMLo > Github : https://github.com/ndb796/python-for-coding-test/blob/master/15/1.java Java 로 구현한 부분

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

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

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

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

[BOJ] 3151. 합이 0 - c++

https://www.acmicpc.net/problem/3151 >풀이 1 투포인터 => 시간초과 >풀이 2 upperbound, lowerbound 사용 풀이 ** lower_bound = 목표값을 포함한 인덱스를 리턴 upper_bound = 목표보다 +1 값의 인덱스를 리턴** `

2022년 1월 23일
·
0개의 댓글
·

10816 숫자 카드2[lowerbound upperbound]

10816 숫자카드2 https://www.acmicpc.net/problem/10816 lowerbound와 upperbound를 이용하여 이분탐색으로 원하는 수를 찾고, 그 수의 개수를 찾을 수 있다.

2022년 1월 15일
·
0개의 댓글
·

10816_숫자 카드 2

lowerbound, upperbound : 이진 탐색으로 원소를 탐색하는 함수 오름차순 정렬된 자료에서 특정 범위에 속하는 숫자들이 몇 개 있는지 탐색할 때 사용 오름차순 정렬된 자료에서 특정한 숫자가 몇 번 나오는지 탐색할 때 사용 lower_bound(arr.begin(), arr.end(), key) - arr.begin(); : 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 upper_bound(arr.begin(), arr.end(), key) - arr.begin(); : 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 (index값 알기 위해서는 arr.begin() 빼야 함) https://www.acmicpc.net/problem/10816

2022년 1월 6일
·
0개의 댓글
·

BOJ - 18870 좌표 압축

여러 수 중 자신보다 작은 것들의 갯수를 구하는 문제이다. 단, 작은 것들이 중복되는 경우는 하나로 취급해야 한다. 문제해결 전략 주어진 수들을 정렬한 후 갯수를 세 나가는데, 중복되면 카운트 안하는 방식으로 계산하면 된다. 처음에는 중복을 체크하기 위해 map 자료구조를 이용하였다. (주석부분) 현재 확인하고자 하는 수가 map에 존재하지 않는다면 카운팅 하고 map에 추가해 준다. 위 과정을 마지막 수까지 반복하면 된다. 두번째 방법은 다른 분들의 코드를 참고하였다. algorithm의 unique()를 사용하여 중복된 것들을 뒤로 뺀후 vector의 erase()를 이용하여 뒤의 것들을 제거해 준다. 이 과정에서 중복된 것들을 벡터에서 제거해 준다. 그 다음으로 lower_bound()를 이용하여 key의 위치를 찾아 출력해 주면 된다. 코드 출처 https://www.acmicpc.net/problem/18870

2021년 12월 18일
·
0개의 댓글
·
post-thumbnail

Binary Search : lower bound & upper bound

Binary Search (이진 탐색) 이진 탐색은 정렬이 된 데이터에서 어떠한 특정 값이 존재하는지 검색하는 알고리즘이다. 기준 값을 통해 그 값을 기준으로 데이터를 나누어 탐색한다. 중복된 데이터가 없을 때는 기본적인 이진 탐색을 통해 쉽게 구할 수 있으나, 중복된 데이터들이 있는 경우엔 구할 수 없다. 이를 위해서는 lower bound와 upper bound를 통해 탐색해야 한다. > lower bound : 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치 탐색 가능 > upper bound : 데이터 내에서 특정 값보다 처음으로 큰 값이 나오는 위치 탐색 가능 참고 : [cherishee's tistory](https://hee96-stor

2021년 10월 12일
·
0개의 댓글
·

백준 18870번 문제를 풀며 배운것들

unique함수는 연속으로 중복되는 원소를 제거하는 함수이다. 구체적인 작동방법은 다음과 같다. v=3 4 4 2 1 2 5 일때 v를 sort 함수를 통해서 정렬하면 v=1 2 2 3 4 4 5 이고 unique함수에 넣으면 연속으로 중복되는 원소들이 사라지고 남은 원소들을 앞에서부터 순서대로 채워넣고 남은 자리에는 원본의 원소를 그대로 가져다가 쓴다. v = 1 2 2 3 4 4 5 에서 하면 v = 1 2 3 4 5 4 5가 된다. 이제 원본의 원소를 그대로 가져다가 쓴 부분만 지우면 중복된 원소가 하나도 없는 정렬이 완성되는데 unique 함수는 원본의 원소를 그대로 쓴 첫번째 주소를 반환하기 때문에 를 실행하면 v = 1 2 3 4 5가 됨을 알 수 있다. lowerbound는 이진 탐색으로 원소를 탐색하는 함수이다. 탐색을 진행하려는 정렬이나 vector가 정렬 되어 있어야 사용할 수 있으며 lowerbound의 용도는 찾으려는 ke

2021년 9월 23일
·
0개의 댓글
·
post-thumbnail

[프로그래머스] 순위 검색 (python 파이썬)

👉 순위 검색 ✍ 내 코드 (효율성 미통과 코드) ✍ 내 코드 (통과 코드) ![](https://images.velog.io/images/coding_egg/post/c194a

2021년 5월 7일
·
0개의 댓글
·

2021.04.25 TIL 🔼

도전하는 당신 아름답다! 오랫만에 다시 ps를 풀자. 이번에는 골드 5!! 😈 이분탐색에 있어서 어느정도는 안다고 자만한 나머지, 골드5를 풀어보고 싶었다. 문제는 다음과 같은데 투 포인터를 사용한다고 분류가 되어있었다. 투포인터에 대한 개념은 참조블로그에서 잘 나와있다. 역시나 이 포기하는 습관을 버리기가 힘들다. 원래는 한시간만 하고 안되면 과감히 다른 사람의 코드를 볼랬는데 이번에도 내가 하는 방법이 당연히 맞는거 같아서 왜 틀렸는지 조금만 더 보자고 하다가 2시간가까이 붙잡게 되었다. 이 때는 투 포인터 개념도 몰라서 이분탐색을 while문으로 돌리는 것이었는데, 결국 해결하지 못하고 다른 사람의 코드를 봤다. 요즘 내가 이웃한 현무님이 [해답법](https://blog.naver.com/gust

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

백준-10816 숫자카드 2

문제 😀 BS를 이용해서 풀려했는데 시간초과로 풀수가 없었다. 그래서 풀이법을 찾는중 lower bound와 upper bound의 개념을 찾게되었다. 개념 😃 lower bound는 타겟인 수보다 크거나 같은 최초 위치를 찾아내고 upper bound는 타겟인 수보다 초과인 최초 위치를 찾아낸다. 물론 lower bound와 upper bound도 BS와 같이 데이터가 정렬이 되어있어야한다. 1 2 2 4 5 5 5 8 10 의 수열이 있다고 하자. 이중에서 target이 5의 lower bound와 upper bound를 찾아보자 lower bound 1 2 2 4 5 5 5 8 10 , 앞에서부터 5번째 있는(리스트라고 생각하면 인덱스가 4인)이 5가 lower bound의 값이다. upper bound 1 2 2 4 5 5 5 <span style="colo

2021년 3월 3일
·
0개의 댓글
·
post-thumbnail

Java로 upper_bound와 lower_bound 구현하기

어떤 리스트에서 이분탐색을 이용해서 특정 값을 찾을때, 리스트가 중복된 값을 포함하고 있을 수 있다. 그 중복값을 전부 찾거나 또한 그 중복값들을 활용해서 문제를 해결하는 문제를 위해서 upperbound나 lowerbound가 존재한다. 역시나 마찬가지로 이 함수는 c++의 Algorithm.h 헤더에서 제공해준다. 이를 참고해서 java에서 구현해보도록 하자. lower_bound 범위 [begin, end) 안의 원소들 중, 특정 target보다 크거나 같은 첫번째 원소의 인덱스를 리턴한다. 만약 그런 원소가 없다면 end 인덱스를 리턴한다. 이때 리스트는 모두 정렬된 상태여야 한다. 즉, lower_bound가 성립하기 위해서는 각각의 요소들중 element < target를 만족하는 요소들은 만족하지 않는 요소들보다 앞에 있어야한다. c++의 lower_bound를 확인해보면 아래와같이 구성되어있다. 인자로 (리스트의 시작, 리스

2020년 6월 9일
·
0개의 댓글
·

2019 winter PS --version DP (day6)

백준 11053, 11054 -- 1) 백준 11053 : 가장 긴 증가하는 부분수열 (https://www.acmicpc.net/problem/11053) LIS문제. 이전에 풀어봤었어서 반가웠다. 참 볼때마다 대단하다고 느끼는 문제. 구하고자 하는 것은 수열의 크기이므로 이것에 집중한다. LIS라는 벡터에 입력값들을 저장하는데 크기가 크면 이어 붙이면 되지만 더 작을 경우 생각을 해야 한다. 작을 경우에 이것을 선택할지 말지를 결정해야 하는데 그것을 벡터 내부에 삽입하는 것으로 대체한다. 이렇게 되면 이 수를 선택하는 경우도, 선택하지 않는 경우도 모두 따질 수 있기 때문이다. 예를들어 입력값에 따른 벡터내부의 변화를 봐보자. 6 10 20 10 30 20 50 라는 입력이 있을 때, 벡터는 순차적으로 (10) : {10} (20) : 10 {20} (10) : {10} 20 (30) : 10 20 {30} (20) : 10 {20} 30 (50) : 10 20 30 {50

2019년 12월 29일
·
0개의 댓글
·