# 이분탐색
[카카오] 시험장 나누기
최대 노드 수: 10000개그룹을 최대 몇 개까지 나눌 수 있는지: 10000개완전 탐색 시 10000! \* 10000^2따라서 각 합에 대한 정보를 memoryzation 해야 하고 검색을 빠르게 해야 한다. 일단 다이내믹 프로그래밍으로 풀어야 할 것 같은 생각이
백준 2470번 두 용액 파이썬
문제 입력 , 출력 solution 설명 키포인트 > 1. 이분탐색 , 투포인터를 사용해서 풀이 mid값으로 하지 않고 left , right만 사용함 두 값을 더했을 경우 0보다 작은경우 0보다 같거나 큰경우는 오른쪽 포인터에 인덱스를 1씩 더해준다. 두가지
백준 1939 | 중량제한 (BFS, 이분탐색) | 파이썬
n 개의 섬으로 이루어진 나라가 있다.이들 중 몇 개의 섬 사이에는 다리 설치되어 있어 차들이 다닐 수 있다.두 개의 섬에 공장을 세워두고 물품 생산한다.물품을 생산하다 보면 공장에서 다른 공장으로 생상 중이던 물품을 수송해야 할 일이 있다.각각의 다리마다 중량 제한이
백준 1300번 k번째 수 파이썬
k번째 수는 최대 k값을 가짐k번째의 수 보다 작은 수의 개수를 찾음mid의 값보다 작은 수의 개수는EX) 3 3 에서 7보다 작은 수의 개수는11 ~ 13 = 3개 = min(n,7/1) = 321 ~ 23 = 3개 = min(n,7/2) = 331 ~ 3\*2
[WEEK02] DAY12 & TMI
오늘은 오전에 몸 상태가 안좋았어서 약찾아먹고 해결하고 한다고 좀 부산했고,,,낮까지 기초 문법좀 다시 잡았다그리구 저녁먹기 전쯤부터 알고리즘 풀기 시작이번주 문제리스트의 첫 시작은 이분 탐색 !import sysinput=sys.stdin.readlinen, min_
[프로그래머스] 예산
https://programmers.co.kr/learn/courses/30/lessons/12982주어진 예산 안에서 모든 도시에 최대한 돈을 줄 수 있는 상한선을 구한다도시의 비용을 오름차순으로 정렬한 뒤, 도시 인덱스를 기준으로 이진탐색. 상한액이 bud
10816 숫자카드 2
카드 개수와 카드 번호를 입력받는다.(해당 번호를 정렬한다.)카드 개수를 저장할 딕셔너리를 입력받는다.찾아야되는 카드 번호를 입력 받는다.key 값이 존재하면 해당 key값의 value를 답을 담아둘 result배열에 추가한다.문제가 원하는 출력대로 빈칸" "을 넣어서
모두 모여 K
1학년 A반에는 총 명의 학생이 있다. A반 학생들은 이번 축제 수학과에서 개최한 반 대항전에 출전하기 위해 연습 중이다. 반 대항전에 참가하면 A반의 학생들은 각자 고유의 숫자를 받게된다. 대항전은 A반의 학생이 최소 명, 최대 명의 임시 그룹을 결성, 그룹 내 학생들의 고유 숫자를 합해 주최측에서 제공하는 숫자 를 만들 수 있는지 확인하는 게임이다. 예...
[2021 카카오 블라인드 테스트] 순위 검색
문제각 지원자의 info가 가지고 있는 4가지의 조건으로 만들 수 있는 경우의 수는 16가지다. 예) 언어: java냐 아니냐, 직군: frontend냐 아니냐 ... -> 2 2 2 \* = 16 이 경우의 수들을 딕셔너리의 키 값으로 저장하고, 그 키 값에 대한
이분탐색
원소가 정렬되어 있는 상태여야 한다.lower bound : 찾고자하는 값보다 크거나 같은 값이 처음 나오는 인덱스일반적인 이분 탐색과 같다.
알고리즘 | 이분탐색 개념과 예제 + 심화
📌 개념 다지기 이분 탐색 탐색 기법중 하나로, 탐색하고 싶은 범위를 두 부분으로 분할해서 찾는 방법이다. 두 부분으로 계속 분할해서 조건에 맞는지 찾아가기 때문에, 시간 복잡도가 O(log n)으로 매우 빠른편이다. ✔️탐색하는 방법 배열이 정렬(sort
백준 파이썬 2805번
https://www.acmicpc.net/problem/2805(시간 초과)나무 리스트에서 가장 높은 나무의 높이를 h라하자.h-1부터 cut을 실행해서 최초로 M보다 크거나 같은 값이 나온다면 그 높이가 최댓값이 된다.이 작업을 높이 0으로 cut할 때까지
백준 알고리즘 18870번 : 좌표 압축
https://www.acmicpc.net/problem/18870주어진 배열을 정렬해주고 중복을 제거한 후에 lower_bound를 활용해서 이분탐색을 진행해주면 됩니다.
백준 알고리즘 1920번 : 수 찾기
https://www.acmicpc.net/problem/1920이분탐색의 STL을 활용해서 있는지 없는지 판별해주면 됩니다.