binary search10 [자바] 백준 14786 - Ax+Bsin(x)=C ② (java) 목차 문제 : boj14786 필요 알고리즘 수학, 이분 탐색 이분 탐색으로 답의 범위를 좁혀가며 상대 오차 10^-9 이하로 찾아주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 처음에 문제보고 일단 수식이 나오니 무서웠는데, 어차피 y=x랑 y=sin(x) 합친 형태라 대충 그래프 형태가 상상이 되기도 하고, 입력값 범위도 좁아서 도전해보니 생각보다 어렵진 않았다. 풀고보니 '뉴턴-랩슨법' 이라는걸로 풀면 바로 .. 2024. 4. 5. [자바] 백준 3089 - 네잎 클로버를 찾아서 (java) 목차 문제 : boj3089 필요 알고리즘 매개변수 탐색(Parametric Search), 이분탐색, 정렬 2차원에 대한 매개변수 탐색(이분탐색 응용)으로 풀 수 있는 문제이다. 이걸 위해 정렬이 필요하다. 시뮬레이션 M개의 명령에 대해 시뮬레이션을 돌려봐야 최종 결과를 알 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 R, L, U, D 각각의 명령에 대해 필요한 동작은 다음과 같다. R : 동일 Y축에서 우측.. 2024. 2. 22. [자바] 백준 1477 - 휴게소 세우기 (java) 목차 문제 : boj1477 필요 알고리즘 매개 변수 탐색 (parametric search), 이분 탐색 (binary search) 이분 탐색을 이용한 매개 변수 탐색으로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 2년전에 못풀었다고 되어 있는데, 이번엔 어렵지 않게 풀었다. 발전하긴 한 것 같아서 기분 좋았다. 최소가 되는 구간을 직접 찾으려면 상당히 난감해진다. 그리디처럼 구간이 크다고 무조건 세운다.. 2023. 12. 8. [자바] 백준 19845 - 넴모넴모 2020 (java) 목차 문제 : boj19845 필요 알고리즘 이분 탐색 의외로 이분 탐색 문제이다! 물론 다른 방법들도 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제 설명이 좀 복잡해서 그렇지 잘 생각해보면 해야하는건 단순한 편이다. 배열 arr에다가 arr[1]부터 arr[n] 까지에 입력으로 주어진 N개의 정수 a를 순서대로 담아두었다고 해보자. 우선 오른쪽으로 나가는 레이저로 몇 마리가 제거되는지만 생각해보자. 이 경우 입.. 2023. 7. 22. [자바] 백준 28276 - Yawned-Zoned (java) 목차 문제 : boj28276 필요 알고리즘 이분 탐색(binary search), 매개 변수 탐색(parametric search) 이분 탐색을 응용한 매개 변수 탐색 알고리즘 문제이다. 흔히 결정 문제라고 부르는 형태의 문제이다. 물론 결정 문제로 어떻게 만들지는 아이디어가 떠올라야 하긴 하다. 분리 집합(disjoint set) 결정 문제로 풀고자 할 경우, 분리 집합을 써야 효율적으로 짤 수 있다. 애초에 시간 제한이 빠듯한 문제라 다른 방법으론 통과가 힘들 것 같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보.. 2023. 7. 18. [자바] 백준 2343 - 기타 레슨 (java) 목차 문제 : boj2343 필요 알고리즘 매개 변수 탐색 (parametric search), 이분 탐색 (binary search) 이분 탐색을 응용한 매개 변수 탐색을 사용해 푸는 문제이다. 이런류는 매개 변수 탐색할 값에 대한 정의만 잘 세우면 갑자기 문제가 쉬워진다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일단 순차적으로 생각해보자. 1. 우선 isPossible(int limit) 이라는 함수를 생각해보자... 2023. 7. 17. [자바] 백준 25393 - 교집합 만들기 (java) 문제 : boj25393 필요 알고리즘 개념 이분 탐색 (binary search) 이 문제에서 매개 변수 탐색 알고리즘을 사용하기 위해 기본적으로 알아야 한다. 매개 변수 탐색 (parametric search) 이분 탐색에서 약간 응용된 알고리즘이다. 이분 탐색은 값 A를 찾는 것이고, 매개 변수 탐색은 값 A를 찾을 수도 있고, 그 보다 크거나 작은 수의 위치도 찾을 수 있다. 해시를 사용한 집합과 맵 자바를 기준으로 해시맵 자료구조를 알고 사용할 줄 알아야 한다. 애드 혹 애드 혹 문제이다. 이게 뭐냐면 그냥 아이디어 상품같은거라고 생각하면 된다. 보통 정형화된 방법으로 풀리지 않고 아이디어가 필요한 문제에 태그로 붙곤한다. 어찌보면 그리디에 가깝다. 이게 태그에 달려있다고 그걸보고 풀 수 있는건.. 2022. 8. 10. 백준 18384 자바 - PRIM (BOJ 18384 JAVA) 문제 : boj18384 이 문제를 풀기 위해 코드적으로 알아야 하는 것은 다음의 두가지 이다. 1. 1000000보다 처음으로 큰 소수까지의 모든 소수 2. 특정 입력에 대해 빠르게 그보다 작지않은 소수를 구하기 '1'의 경우 에라토스테네스의 체로 구할 수 있다. 참고로 1000000보다 처음으로 큰 소수는 1000003이다. 이건 정확히 몰라도 된다. 대충 1000100 까지 구하면 된다. 참고로 n이하의 모든 소수를 알기위해 에라토스테네스의 체를 사용할 때는 sqrt(n) 까지만 확인하면 된다. 이것에 대한 설명 및 증명은 이 글('에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유')에 있다. '2'의 경우 이분탐색을 활용하면 된다. c++의 upper_bound에 해당하는걸 .. 2022. 3. 22. 백준 1450 자바 - 냅색문제 (BOJ 1450 JAVA) 문제 : boj1450 1. 문제 접근 딱히 냅색과 관련없어 보이는 문제이다. N이 작아 쉽게 풀 수 있을 줄 알았다. 근데 당연하게도 모든 경우를 보면 O(2^30) 이므로 통과할 수 없다. 그렇다고 냅색처럼 DP로 풀자니 1~10^9 까지 확인해야 할 것 같으니 역시 통과할 수 없다. bit DP쪽으로도 딱히 떠오르지 않았다. 그래서 이 문제에서 적용한 방식처럼 반반을 나눠서 생각해보기로 했다. 1.1 최대 30개의 데이터를 대충 반반으로 15개씩 나눈다(사실 한쪽을 25개, 한쪽을 5개로 해도 상관없다.). 이걸 A와 B라 하겠다. 1.2 A에 대해 나올 수 있는 모든 무게 합의 경우의 수 확인하고 어딘가에 저장한다. 이 경우 최대 15번에 대해 해당 수를 포함하거나 포함하지 않거나의 2가지 경우이.. 2022. 1. 22. 백준 1365 자바 - 꼬인 전깃줄 (BOJ 1365 JAVA) 문제 : boj1365 이 단어를 제가 쓰게될줄은 몰랐는데.. 'Well-Known'한 문제이다. DP쪽엔 냅색류가 유명하듯, 이분탐색쪽도 뭔가 선 꼬인거에서 안꼬이게 최대치 이런 종류의 문제가 유명하다. 사실 이런 류의 문제를 접해보지 못했다면 아이디어를 떠올리기 힘들 수 있다. 아이디어는 어떨 때 꼬이는지를 확인해보면 된다. -> 간단히 순서대로 선을 이어줄 때, 직전에 들어왔던 입력값보다 작은 값이 입력되면 꼬이게 된다. 예를들어 아래와 같은 경우 좌측의 순서대로 우측에 매칭된 숫자는 1, 3, 4, 2가 된다. 이 때 꼬인 부분은 이전보다 작은 값이 들어온 [4, 2] 부분이 된다. 그럼여러 경우를 테스트 해보면, 위와 같이 서로 겹치지 않게(안꼬이게) 하려면 단순히 subsequence(1,3,.. 2021. 12. 1. 이전 1 다음
