# 이분탐색

21개의 포스트

[프로그래머스] 입국심사

생각을 조금 해야하는 바이너리 서치 문제

2020년 10월 16일
·
0개의 댓글
post-thumbnail

[이분탐색] 징검다리

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있다. 그리고 그사이에는 바위들이 놓여있다. 바위 중 몇 개를 제거하려고 한다.바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성하라.dista

2020년 9월 21일
·
0개의 댓글
post-thumbnail

[이분탐색] 입국심사

n명이 입국심사를 위해 줄을 서서 기다리고 있다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다르다.처음에 모든 심사대는 비어있다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수

2020년 9월 11일
·
0개의 댓글
post-thumbnail

[BOJ]17503: 맥주 축제

17503: 맥주 축제내일부터 N일 동안 대구광역시에서 맥주 축제가 열립니다!이 축제에서는 무려 K종류의 맥주를 무료로 제공합니다.축제 주최자는 축제에서 더 많은 참가자들이 다양한 종류의 맥주를 즐겼으면 합니다. 그래서 축제에서 참가자들은 하루에 맥주 1병만 받을 수

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

예산 (python)

입력 값이 큰 경우, 이분탐색 중 최대값 구하는 문제

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

입국심사 (python)

입력 값이 큰 경우, 이분탐색 중 최소값 구하는 문제

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

가사 검색 - 2020 카카오 공채 (python)

효율성 테스트 뚫기가 관건인 문제, 이분 탐색이용, bisect 모듈 사용

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

백준 10816번: 숫자 카드2

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수

2020년 8월 28일
·
0개의 댓글
post-thumbnail

이분 탐색(Binary Search)

이분 탐색(Binary Search)는 오름차순 혹은 내림차순으로 정렬된 수열에서 검색하는 알고리즘이다. 선형 탐색보다 훨씬 빠르게 탐색할 수 있다는 장점이 있다. 시간복잡도는 탐색할 범위를 절반으로 줄여서 탐색하므로 O(logn)이다.이분 탐색은 아래와 같은 과정으

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

백준 1920번: 수 찾기

문제N개의 정수 A1, A2, …, AN이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.입력첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A1, A2, …, AN이 주어진다. 다음 줄에는 M(1≤

2020년 8월 12일
·
0개의 댓글

백준 2869번: 달팽이는 올라가고 싶다

문제땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리

2020년 8월 11일
·
0개의 댓글
post-thumbnail

Java로 upper_bound와 lower_bound 구현하기

어떤 리스트에서 이분탐색을 이용해서 특정 값을 찾을때, 리스트가 중복된 값을 포함하고 있을 수 있다. 그 중복값을 전부 찾거나 또한 그 중복값들을 활용해서 문제를 해결하는 문제를 위해서 upper_bound나 lower_bound가 존재한다.

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

[pwnable.kr] coin1

문제 링크당신의 손에 몇개의 황금 코인이 주어졌습니다. 하지만, 그 중 한개의 가짜 코인이 있습니다. 위조코인은 진짜 코인과 똑같이 생겼습니다. 다만, 가짜 코인의 무게는 진짜 코인의 무게와 다릅니다. 진짜 코인의 무게는 10, 가짜 코인의 무게는 9 입니다. 저울을

2020년 3월 1일
·
0개의 댓글

[프로그래머스] 징검다리 (Java)

프로그래머스 징검다리문제에서 묻는 바를 다르게 생각할 수 있어야하는 것 같다. 문제에서는 돌을 n개 만큼 없앴을 때 시작점, 끝점, 돌 사이에 거리 중 최솟값 중에 최댓값을 구하라고 한다. 묻는 바를 반대로 생각하여 n개의 돌을 없애서 돌 사이 거리의 최솟값이 x로 만

2020년 2월 26일
·
2개의 댓글

[프로그래머스] 입국심사 (Java)

프로그래머스 입국심사기본적인 이분탐색 문제였다. 이분탐색 문제는 제한사항에 주어지는 숫자가 굉장히 크고 최댓값 또는 최솟값을 구하는 경우가 많다. 이 문제에서는 모든 인원이 입국심사를 통과할 수 있는 시간의 최솟값을 구하는 문제다. 구성은 일반적인 형태를 띄고있고 다음

2020년 2월 26일
·
0개의 댓글

[BOJ 1939] 중량제한 (Java)

BOJ 1939 중량제한이분탐색을 풀고있어서 이분탐색 + BFS로 풀었지만 다시보니 크루스칼로 푸는게 더 쉬울거 같다.1\. left를 1, right를 다리의 하중 중에 최댓값으로 두고 이분탐색을 실시한다.2\. mid 값을 바탕으로 BFS 그래프 탐색을 수행해서 목

2020년 2월 24일
·
0개의 댓글

[BOJ 1654] 랜선 자르기 (Java)

BOJ 1654 랜선 자르기기본적인 이분탐색 문제로 N개의 랜선들을 같은 길이의 랜선으로 자르는데, K개를 넘는 최대 개수가 되는 길이를 구하는 것이다. 1\. 주어진 랜선을 길이 기준 오름차순으로 정렬한다.2\. 최소 1, 최대 주어진 랜선 중 가장 긴 길이를 시작으

2020년 2월 24일
·
0개의 댓글

[BOJ 7453] 합이 0인 네 정수 (Java)

BOJ 7453 합이 0인 네 정수 문제풀이 BOJ 2143 두 배열의 합의 아이디어를 그대로 사용하였다. A[]와 B[]를 합하는 모든 경우 AB[], C[]와 D[]를 합하는 모든 경우 CD[] -AB[]를 CD[]에서 찾기, 이진탐색(중복 값이 있으므로 uppe

2020년 2월 4일
·
0개의 댓글

[BOJ 2143] 두 배열의 합 (Java)

BOJ 2143 두 배열의 합 문제풀이 주어진 A, B 배열에서 각각 합하여 나올 수 있는 모든 경우의 합을 리스트에 담는다. 첫 번째 리스트를 돌며 T - list[i] 가 두 번째 리스트에 있는지 확인한다. 어려운 문제였다... 모든 합의 경우를 가지고 있는 리

2020년 2월 4일
·
0개의 댓글

2019 winter PS --version Basic (day13)

백준 10815 -- 1) 백준 10815 : 숫자카드 (https://www.acmicpc.net/problem/10815) 처음에는 상근이의 카드를 a 입려값을 b로 한 후 두 어레이를 모두 sort하고 curser를 두개 둬서 점점 이동시키는 방법을 생각했었는데 입력 순서에 따라 답을 줘야 해서 이 방법은 채택하지 않았다. 나머지 할 수 있는 것은...

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