Noooodle's Footprints

이진탐색을 이용해 주어진 값보다 작은 범위를 찾아서 합했다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class BOJ7795 { public static int countBigger(int[] arrA, int[] arrB, int N, int M){ int i, low, high, cnt = 0, mid = 0; for(i=0;i

이진탐색 문제 왤케 어렵지.. 연속해서 풀어도 감 잡기가 힘들다. 집에다가 공유기를 C개 설치하는데, 설치된 집 사이 거리들 중, 거리가 좁은 쪽을 구한다. 좁은 쪽의 거리들 중에 최댓값을 찾는다. 아래는 예시이다.*은 공유기이다. 설치를할때..  1 2   4        8 9  -> 이런식으로 하면 최소거리는 1이다(1~2)  * *   * 1 2   4        8 9  -> 최소거리는 3(1~4)  *      *         * 1 2   4        8 9  -> 최소거리는 3(1~4)  *      *           * 1 2   4        8 9  -> 최소거리는 1(8~9)  *                * *이 중 제일 큰 최소거리인 3(1~4)가 답이다! 뭘 탐색..

이진탐색을 활용한 세 번째 문제이다. 연달아 푸니 이진탐색 문제에서 중요한게 뭔지 느껴진다.. 제일 중요한건 이진탐색할 범위이다. 범위를 잘못 정하면 아무리 이진탐색을 해도 정답을 맞출 수 없다. 질문게시판을 보니, 문제가 이해 안된다는 글이 매우 많았다.. 예전에는 더 복잡하게 문제가 적혀있었나? 아무튼.. 지금 돈이 있으면 쓰고, 없으면 출금한다. 근데 그냥 출금하면 안되고 지금 있는 돈 다시 통장에 다 넣어서 0원 만들고 출금해야한다. 문제에서 준 예제 7 5 / 100 400 300 100 500 101 400 으로 입출금내역을 정리하면 아래와 같다. *는 출금, -는 사용한 돈, = 는 돈 쓰고 남은 현재돈*+500 // 첫 출금-100 // 첫째날 100원 씀=400 // 400원 남음-400..

앞서 한 나무자르기와 비슷한 문제이다. 이진탐색을 이용했고 나무자르기처럼 답이 딱 안 떨어질 때가 있다. 여유있게 잘라줘야한다.(예: 1 3 / 4 인 경우.. 원하는 답은 3 -> 2로 자르면 2개나오고 1로 자르면 4가 나옴, 답은 1) 1. 입력 받고 정렬2. 이진탐색을 이용해 특정값으로 잘라서 몇 개 나오는지 확인하기3. 출력 1. 3. 은 생략 2. 이진탐색을 이용해 특정값으로 잘라서 몇 개 나오는지 확인하기 처음 이진탐색 범위는 1~제일 긴 랜선 길이(Lan[K-1])이다. 1개 이상은 나와야 몇개가 나오는지 셀 수 있기 때문이다.. 문제에서 준 예제는 4 11 / 802 743 457 539 이고, 제일 긴 랜선은 802이므로 1 ~ 802로 이진탐색을 한다. 이진탐색의 조건은 mid로 잘랐..

심하게 삽질 한 문제!!! 난 바보다... 이진탐색을 한다. 문제에 있는 예시처럼 10 15 17 20 배열이 있다면, 0 ~ 20으로 이진탐색을 한다. 처음에는 mid가 10이 됐다가.. 값 크기 차이를 보고 앞부분을 탐색하거나 뒷부분을 탐색한다. 이진탐색 쓰기로 정했을때 그 생각을 못하고 배열자체를 이진탐색해서 정확하게 찾은 경우, 못찾은경우에 mid들을 비교해서 1개씩 비교하고.. 어쩌고.. ㅎ.. 심지어 제일 처음에 풀때는 브루트포스로 풀었고 다른 예시는 다 적용이 되나 나무 크기가 중복되는 경우(10 10 10  1. 입력받고 정렬 -> 이진탐색 해야되니까..2. 이진탐색으로 적절한 값 찾기3. 출력하기 1. 3. 은 생략.. 2.만 추가설명 2. 이진탐색으로 적절한 값 찾기위에서 말한대로 0부..

입력은.. 주어진대로 받으면 되고, 집합 S에 문자열들이 있는지 확인할때 이진탐색을 쓰면 된다. 주의사항은 이진탐색은 정렬된 상태에서 가능한 탐색방법이므로, 정렬 후 이진탐색을 하면 된다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamR..