# Binary Search
[백준] 6236 용돈 관리
6236 용돈 관리첨에 문제 읽고 이게 뭔소리야... 싶었는데그냥 2343 기타 레슨 문제랑 비슷한 문제인 것 같다돈이 모자라면 다시넣고 어쩌구 더 남더라도 M번을 맞추기 위해 어쩌구기타 레슨 문제로 생각하면 걍 강의를 순서대로 녹화해야 하고 (날짜 순서대로 돈을 씀)
[백준] 2776 암기왕
2776 암기왕책에 있는 부품 찾기 문제랑 비슷하다전통적인 이진탐색 개념대로 입력받은 수를 정렬하고 찾으면 된다여기서는 수첩 2에 적혀있는 숫자의 순서를 지키면서 수첩 1에 있는지 확인하면 되니까 수첩1 숫자들만 정렬하고 풀었다
[백준/파이썬/이진탐색] 9주차 문제풀이 (#2512,#1072,#2343,#2776,#6236)
기존 풀었던 문제와 유사해서 무난하게 풀었습니다!다른 점은 예산 배정하는 방식이 좀 달랐던 것 같은데상한액을 정해놓고, 그거보다 작으면 기존 금액, 그거보다 크면 상한액으로 예산을 배정하는 것!이를 아래처럼 조건문을 통해 구현하였습니다승률은 백분율로 변환한 후 버림 하
[백준] 2343 기타 레슨
2343 기타 레슨처음에 문제 읽고 이게 뭔소리야... 함힌트 유심히 읽어보고 이해했다구해야 하는 것 : 강의를 다 녹화할 수 있는 블루레이의 최소 크기(start = 0, end = 강의 길이 총합)1번을 구하는데 필요한 기준 : 블루레이 크기에 따라 강의를 '순서대
[백준] 1072 게임
1072 게임구해야 하는 것 : 몇 번의 게임을 더 해야 승률이 오르는지 (지는 경우는 없기 때문에 승률이 변하는 경우는 오르는 경우밖에 없다.)1번을 구하는데 필요한 기준 : 승률형택이는 게임에서 지지 않으므로 이미 승률이 100인 경우에는 절대 변하지 않는다.\->
[백준] 2512 예산
2512 예산책에서 본 떡볶이 떡 만들기 문제랑 비슷한 것 같다백준에서는 2805 나무 자르기, 1654 랜선 자르기 문제와 유사함!정민언니가 알려준 방법으로 알고리즘을 생각해봤어요구해야 하는 것 : 정해진 총액 이하에서 줄 수 있는 가능한 한 최대의 예산 (한 부서
이분 검색(binary search) in C++
Vmid == want_to_find : 찾고자 하는 원소를 찾았을 때이다.Vmid > want_to_find : 찾고자 하는 원소가 더 작을 때, 따라서 rt = mid -1;Vmid < want_to_find : 찾고자 하는 원소가 더 클 때, 따라서 lt =
[백준 1920] 수 찾기_자바Java
https://www.acmicpc.net/problem/1920재귀를 이용한 Binary Search로 문제를 해결했다.문제에서 N의 범위는 (1 ≤ N ≤ 100,000), M의 범위는 (1 ≤ M ≤ 100,000)로 나타냈기 때문에 brute force
[ BOJ / C++ ] 13397번 구간 나누기 2
이번 문제는 이분탐색을 통해 해결하는 문제였다. 이분탐색의 범위에 대해서 고민을 많이 했던 것 같다. 이분탐색의 범위는 0과 배열의 최대값으로 하였다.배열을 돌며 해당 인덱스에서의 최대값-최소값의 값이 mid보다 크다면 cnt를 증가시켜주고, cnt가 m보다 작거나 같
[ BOJ / Python ] 1477번 휴게소 세우기
앞서 C++로 풀어봤던 문제를 파이썬으로도 풀어보았다. 확실히 파이썬이 코드 길이는 짧게 나오는 것 같다.\[ BOJ / C++ ] 1477번 휴게소 세우기휴게소 위치 배열을 오름차순으로 정렬한다.휴게소 거리 배열 dis를 구한다.이분탐색 안에서 mid와 dis를 비교
[ BOJ / C++ ] 1477번 휴게소 세우기
이번 문제는 이분탐색으로 해결하는 문제였다. 처음에는 이분탐색으로 해결하는 방법이 생각이 안나서 이분탐색을 빼고 생각해보았다.각 휴게소 간의 거리 배열 dis를 만든다.dis를 내림차순으로 정렬한다.가장 큰 거리를 반으로 자른다. (휴게소를 사이에 세운다.)dis를 다
[Algorithm] 이진탐색(binary search)
이진탐색(binary search)리스트에서 특정 수를 찾는데 쓰이는 알고리즘단순히 n개의 리스트에서 x를 찾기 위해서는 간단하게 O(n)의 시간복잡도로 풀 수 있는 방법이 있음(리스트를 전체 탐색해보면 됨). 그러나, 이 방법은 n = 1억이 되는 순간 너무나도 커지
[백준] 3079 입국심사
구글링했습니다..X시간동안 한번 심사에 5초 걸리는 심사관이 검사할 수 있는 사람 수는 X/5명이다.해당 방법을 기억하고, 각각의 심사관들이 X시간동안 검사할 수 있는 사람의 합이 전체 명수보다 크거나 같으면, 현재 가장 작은 시간과 비교하여, 작은 것을 result에
[백준] 1654 랜선 자르기
링크텍스트2805 나무 자르기 문제와 동일하게 랜선의 길이를 범위로 해서 이진탐색으로 풀이했다.1\. 0부터 랜선의 최대 길이까지를 이진 탐색의 범위로 설정한다.(start = 0, end = max(line))2\. mid = (start + end) // 2 의 길
[백준] 2805 나무 자르기
2805 나무 자르기원래 이진 탐색의 개념은 정렬된 배열 또는 트리에서 인덱스 범위를 좁혀가며 값을 찾는 거지만, 여기서는 나무의 길이 자체를 인덱스로 활용하여 인덱스가 곧 답이 되는 방식으로 풀었다.1\. 0부터 나무의 최대 길이까지를 이진 탐색의 범위로 설정한다.(
[ BOJ / Python ] 16564번 히오스 프로게이머
이번 문제는 이미 C++로 구현한 문제이다. 파이썬 연습을 위해 파이썬으로 다시 작성해보았다. 이분탐색을 이용한 문제이다.
[ BOJ / C++ ] 2143번 두 배열의 합
이번 문제는 누적합을 구한 뒤에 이분탐색을 통해 경우를 찾는 문제였다. 여러번 시도 끝에 해결하였는데 처음에는 다음과 같이 작성하였고 오답처리 당했다.배열 a,b에 대한 누적합 배열 asum, bsum을 구하고 이를 정렬한다.누적합 배열 asum에 대해서 이분탐색을 누
[ BOJ / C++ ] 16564번 히오스 프로게이머
이번 문제는 이분탐색을 통해 해결하였다.우선 범위가 최대 10억이므로 자료형은 long long을 사용한다.입력받은 x중 가장 작은 수를 사용해야 하므로 오름차순으로 sort해준다.이분탐색의 범위는 가장 작은 수인 x0과 x0이 될 수 있는 수 중 가장 큰 수인 x0+