이분 탐색12 [자바] 백준 27650 - 마법박스 (java) 목차문제 : boj27650 필요 알고리즘매개 변수 탐색 (이분 탐색), 에라토스테네스의 체문제에서 제시된 것의 규칙을 찾아, 20번 내에 물어볼 수 있는 방법을 찾아야 한다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 처음엔 무지성으로 단순히 최대 500만개짜리 배열 만들어두고, 2부터 시작하면서 물어보고 1이라고 하면 2의 배수 전부 체크하는 식으로 생각했었다. 문제는 인터랙티브 문제라 틀렸습니다라고 안떴다는 점이.. 2024. 5. 17. [자바] 백준 14786 - Ax+Bsin(x)=C ② (java) 목차 문제 : boj14786 필요 알고리즘 수학, 이분 탐색 이분 탐색으로 답의 범위를 좁혀가며 상대 오차 10^-9 이하로 찾아주면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 처음에 문제보고 일단 수식이 나오니 무서웠는데, 어차피 y=x랑 y=sin(x) 합친 형태라 대충 그래프 형태가 상상이 되기도 하고, 입력값 범위도 좁아서 도전해보니 생각보다 어렵진 않았다. 풀고보니 '뉴턴-랩슨법' 이라는걸로 풀면 바로 .. 2024. 4. 5. [자바] 백준 2473 - 세 용액 (java) 목차 문제 : boj2473 필요 알고리즘 투 포인터 또는 이분 탐색 투 포인터를 쓰거나, 이분 탐색을 써서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 처음 생각난 아이디어는, 어차피 n이 5000이므로 2개를 고정시켜놓고, 나머지 하나의 값을 이분 탐색으로 찾는 방법이었다. 이 경우 O(N^2 * logN). 예를들어 현재 고정시켜둔 2개의 값이 -97와 -2라면, -(-97-2) = 99 .. 2024. 3. 20. [자바] 백준 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. [자바] 백준 1981 - 배열에서 이동 (java) 문제 : boj1981 필요 알고리즘 개념 투 포인터, 이분 탐색 투 포인터 혹은 이분 탐색을 섞은 그래프 탐색 문제이다. 일단 태그는 이분 탐색이긴 한데, 난 투 포인터로 풀었다. 그래프 탐색(BFS, DFS) 투포인터 혹은 이분 탐색으로 제한된 범위 내에서 시작점부터 끝 점까지 탐색이 가능한지 확인해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이하 풀이는 투 포인터를 사용한 풀이이다. 태그를 보니 대부분 이분.. 2022. 12. 13. [자바] 백준 7469 - K번째 수 (java) 문제 : boj7469 필요 알고리즘 개념 정해 : 머지 소트 트리 + 세그먼트 트리 정해는 세그먼트 트리를 응용한 머지 소트 트리로 보인다. 내 경우 : 펜윅 트리 머지 소트 트리를 펜윅 트리로 적용시켜서도 풀 수 있다. 매개 변수 탐색 (parametric search) 이분 탐색의 응용 방법인 매개 변수 탐색이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일반적으로는 대부분 세그먼트 트리에 각 노드를.. 2022. 9. 17. 이전 1 2 다음
