이분탐색 7

[BOJ] 3079 입국심사 (Java)

https://www.acmicpc.net/problem/3079 문제를 읽다보니 너어무 익숙했던,, 프로그래머스 문제와 동일했다https://dev-zsunny.tistory.com/23 99클럽 코테 스터디 3일차 TIL 이분탐색(입국심사)https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 시간의 최솟값을 구해dev-zsunny.tistory.com그래서 금방 풀어서 제출했지만 2%, 13%, 30% 계속  틀렸구,,, 또 자료형 문제였다!!!!!분명 자료형 고려해줬다고 생각했는데, 심사 가..

코테/백준 2024.11.03

99클럽 코테 스터디 6일차 TIL 이분탐색(나무 자르기)

https://www.acmicpc.net/problem/2805 이분탐색 문제를 여러개 풀다보니 이제 문제를 읽으니까 언제 이분탐색을 써야할지 감이 살짝 온다1. 변수 범위가 클 때! (1억 이상)2. 구해야하는 값이 랜덤이 아닌, 특정 기준에 맞춰 지속적으로 범위를 찾아주어야 할 때! 즉 문제에서 구하는 값이 최대, 최소인 경우큰 범위 내에서 특정 값을 범위를 통해 찾아야 할 때 => 이분탐색을 쓰자! 무튼 이 문제는 전에 풀었던 예산과 비슷하게 풀었는데 2%에서 틀려서 당황했다,,여러 테케 만들어서 넣어봐도 다 분명 정답이 나오는데,, 문제는 자료형이었다!!!나무의 길이 M이 최대 20억인데 calc 함수에서 상근이가 집으로 가져가려고 하는 나무의 길이 result가 int형 범위를 넘어가는 것이었..

코테/백준 2024.11.02

[BOJ] 2343 기타레슨 (Java)

https://www.acmicpc.net/problem/2343  글을 읽으면서 블루레이의 크기를 mid로 두고 조건을 만족하는 경우의 최솟값을 구하면 됨을 알 수 있었다.조건은 calc 함수를 통해 arr을 순서대로 탐색하며 현재 블루레이 크기 mid인 경우 만들어지는 블루레이 개수 cnt 를 구해 비교해보면 된다.이때, 블루레이 크기보다 강의의 크기가 커서 담기지 않는 경우를 꼭 고려해주어야 한다.또한, 블루레이가 다 찬 경우 시작값에 현재 강의 시간을 잘 담아서 다시 계산해주어야 한다.마지막으로, 블루레이 개수가 꼭 m과 같아야하는 것이 아닌 작을 때도 고려해서 최솟값을 갱신하면 된다! start 값은 1 end 값은 총 강의 시간을 넘어가진 않을 것이므로, 총 강의 시간으로 설정했다.packag..

코테/백준 2024.10.30

[BOJ] 2512 예산 (Java)

https://www.acmicpc.net/problem/2512 이 문제의 경우 예산액의 범위가 1 이상 100,000 이하여서 굳이 이분탐색이진 않아도 될 거 같긴 하다만, 이분탐색으로 풀었음.지방 예산액과 총 예산액이 주어졌을 때, 해당 총 예산액을 만족하는 최대 예산 상한액을 구하는 문제.그렇다면 이 최대 예산 상한액을 m으로 두고 1 ~ 최대 지방 예산액 사이에서 조건을 만족하는 m 값을 구하면 된다.조건을 만족하는 지 확인하는 코드는 다음과 같다. // 총 예산 계산int sum = 0;// 모든 지방의 예산의 예산 상한액보다 작을 경우 idx의 default값은 n이어야 함int idx = n;// 1. 현재 예산 상한액(m) 보다 작은 지방 예산의 합 = arr[i]원for(int i=0;..

코테/백준 2024.10.29

99클럽 코테 스터디 2일차 TIL 이분탐색(징검다리)

https://www.acmicpc.net/problem/11561   처음에 이분탐색이라는 아이디어를 떠올리는 게 어려운 문제였다,,근데 자세히 보면 N의 범위로 보아 선형탐색은 절대 아니고, 두 번째 점프부터 이전 점프 + 1 긴 거리를 점프한다는 점에서 등차수열을 떠올릴 수 있다.그리고 최대 수이니 결국은 무조건 다음 식을 만족한다. => 다음 점프 = (이전 점프 + 1)그렇다면, 몇 개의 징검다리를 건넜을 때가 최대 징검다리가 될 까? 이 징검다리 수를 m으로 두고 이분탐색을 통해 조건을 만족하는 최대 m 값을 구하면 된다.그리고 조건은, m * (m + 1) / 2기 N의 값에 가장 가까우면 된다. (등차수열의 합 공식 사용)주의점은 N의 최대 범위를 고려하여 자료형을 long으로 사용해야 한..

코테/백준 2024.10.29

[BOJ] 2776 암기왕 (Java)

https://www.acmicpc.net/problem/2776 앞선 문제에 이어 골라본 이분탐색 문제.자신 있게 풀다가 잊고있던 StringBuilder의 위력을 다시금 일깨워주었다,, package BOJ;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class BOJ_2776 { static int T; static int n, m; static int[] arr; static StringBuilder sb; public static void b..

코테/백준 2024.10.28

99클럽 코테 스터디 1일차 TIL 이분탐색(게임)

https://www.acmicpc.net/problem/1072 승률이 달라지기위한 게임 횟수를 구하는 문제였다.처음엔 1부터 탐색했는데 생각해보니 X의 범위를 고려했을 때 최악의 경우 10억까지 탐색해야 했다. O(N)따라서 이분탐색으로 풀어야 하는 문제였다. O(logN) package STUDY;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Day01_BOJ_1072 { static int x, y; static int res; public static void main(String[] ..

코테/백준 2024.10.28