1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 package BruteForce_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = ..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 package Binary_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ3079{ static long N, M, max; static int time[]; public static void ma..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 package Binary_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ2110 { static int N,C; static int ad[];..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 package Binary_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ1072 { static long x, y, z, changeZ; public static void main(String args[]) throws IOException { BufferedRead..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 package Binary_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int line[]; static int N; public static void main..

오답 노트 & 새로 알게 된 점 해당 문제는 매개 변수 탐색 방법을 사용하면 된다. 정해진 총액 이하에서 가능한 최대의 총 예산을 구해라 -> 예산이 n일 때, 정해진 총액을 만족하느냐를 구하면 된다. 여기서 이분 탐색을 실시할 때, e값을 생각해보아야한다. 만약에 e를 M의 최댓값인 10억이라고 잡는다면, 예제 입력2와 같이 총 나라의 예산을 합쳐도 총합 예산보다 작다면 상한액을 10억이라할 수 있기 때문이다. 즉, 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 ..

(처음 시도) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int woodArray[]; static int woodLength; public..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 package Binary_Search; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int note[]; stat..

이분 탐색에 있어서, 숫자가 중복인지 아닌지 알아채는 게 중요하다. 중복이면 HashMap을 사용하고 아니면 그냥 일반적으로 풀면 된다. 가장 많이 하는 실수 중에 하나가 범위가 int형인지 int형을 넘어선 long형인지 잘 구분해야한다. 또한, 이분 탐색은 정렬된 상태에서 해야함을 잊지 말아야한다. O(logN)에 특정 값을 찾을 수 있다. Binary Search, Upperbound, Lowerbound 코드를 작성해보자. Binary Search 처음에 while을 빠져나오는 조건에서 궁금한 점이 생겼다. 어떤 코드는 등호가 들어가고, 어떤 코드는 등호가 들어가지 않았다. 차이점은 등호가 들어가게 되면 ed = mid가 되고 등호가 들어가지 않으면 ed = mid - 1로 설정이 되있다. 1 2..

Map 인터페이스를 구현하는 클래스 - 대표적으로 HashMap, LinkedHashMap, TreeMap이 있다. Map 특징 - map은 key와 value로 이루어져 있고, 두 개의 값이 한 쌍의 데이터로 이루어져 있다. 예를 들어 key에는 이름 value에는 홍길동 이런 식으로 한 쌍의 데이터가 저장되어있다. - 중복을 허용하지 않는다. Map 공통 메소드 boolean containsKey(Object key) - map이 특정 key값을 가지고 있으면 true 리턴 boolean containsValue(Object value) - map이 특정 value값을 가지고 있으면 true 리턴 V get(Object key) - key에 해당하는 value값을 리턴한다. 만약에 key값이 존재하지..

풀이 방법 이 문제를 처음에 풀면서 중복된 것을 생각 못하고 일반적인 이분 탐색으로 풀었다. 당연히 풀리지 않았다. 그래서 중복된 숫자를 배열의 index에 집어넣고 그 배열의 값을 한 개씩 증가시키는 방법을 사용하려 했다. 그러나 예제에 음수가 있는 것을 보고 그 방법이 안된다는 것을 알게 됐다. 그래서 마지막으로 생각한 것이 HashMap이었다. 이 문제를 풀면서 HashMap을 제대로 공부하게 되었다. 만약, 음수가 존재하지 않았다면 index에 집어넣는 방법도 나쁘지 않다고 생각한다. 그리고 이분 탐색하면서 꼭꼭 기억해야 하는 점이 있다면, binarySearch에서 sang[mid] == num 일 때, 꼭 return 해주어야 한다는 점이다. 사용 개념 HashMap / Map / 이분탐색 1..

📌Set 인터페이스를 구현하는 클래스 - HashSet, TreeSet, LinkedHashSet 등 📌Set 특징 -List와 다르게 객체를 중복해서 저장할 수 없다. ex) 20 10 10 30 40 20 10 30 40만 저장됨. 중복해서 저장할 수 없는 대신에 순서가 보장되지 않는다. 📌Set 공통 메소드 boolean add(E e) - 객체 저장 후 성공이면 true, 실패면 false를 리턴 boolean contains(Object o) - 객체가 있는지 여부 리턴 boolean isEmpty() - 컬렉션이 비어있는지 확인 boolean remove(Object o) - 인자로 받은 요소를 삭제한다. int size() - 요소의 개수를 리턴 Object[] toArray() -set을 ..