이분탐색

https://www.acmicpc.net/problem/1300   이문제를 처음 접했을 때 int[][] 배열에 모두 채워넣은뒤그 수들을 int[] 에 집어넣고 이분탐색을 통해 풀어야 하나 라는 생각을 갖게되었다.하지만 조건중 N의 범위가 100000임을 알게되었고 이방법은 안되는 것을 깨닫고 열심히 노가다를 시작   열심히 메모장에 적어가며 공식이나 규칙을 발견하려 하였지만생각해낸건 '구구단인데? ' 까지였고 다른 블로그의 도움을 받아 이분탐색을 활용한 풀이법에 도달할 수 있었다. 우선 내가 알고있던 이분탐색은 오름차순으로 정렬된 배열에서 left 와 right를 활용하여 mid를 선정하고mid값과 목표값을 비교하여 작다면 right는 mid-1이 되고크다면 left가 mid+1이되어 값을 찾아나가..

https://www.acmicpc.net/problem/7453   4 개의 배열 a,b,c,d 가 있을 때 N개의 원소의합이 0이되는 조합의 수를 찾는 문제다.N의 범위가 4000 즉 4000*4000*4000*4000 을 하게되면 쉽게 풀수 있으나시간복잡도 측면에서 시간초과가 날것이 분명하기에풀이방법을 이분탐색을 이용하여 A,B의 배열에서 가능한 조합 16000000개와 C,D의 배열에서 가능한 더한 조합 16000000개를 만들어 두조합의 합이 0이되는경우를세기로 하였다. AB의 배열에서가능한 조합 A와 CD의 배열에서 가능한 조합 B를 순회돌기전 정렬을 통해 A,B배열을 오름차순으로 정렬하고 A의 원소중 -31,-31,-31 처럼 중복되는 경우가 생기면 이를 upperbound lowerboun..

https://school.programmers.co.kr/learn/courses/30/lessons/340212 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   이 문제는 이분 탐색을 활용해 난이도 조정을 통해 주어진 시간 제한 안에서 플레이 가능한 최소 레벨을 구하는 문제를 해결한다. solution 메서드는 난이도의 범위를 설정하고, 이분 탐색을 통해 해당 레벨에서 플레이 시간이 조건을 만족하는지를 검사하며최적의 레벨을 찾는다.calculate 메서드는 특정 레벨에서 플레이 시간을 계산하는 함수다.난이도가 레벨보다 높은 경우, 난이도 차이만큼 추가 플레이 시간이 발생하며,이 시간은 현재 및 이..

이분탐색의 기초적인 예를 들 수있는 문제이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class b2776 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st ; StringBuilder sb = new StringBuilder(); int ..

비트연산자개념을 사용하여 while문 하나로 이분탐색을 구현한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.r..