이분탐색5 [백준] 이분탐색 - 1637번: 날카로운 눈 (Java) https://www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어볼 수 있는 날카로운 눈을 가진 기이한 원숭이였다. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다. 어느 날 멍멍이는 원숭이의 날카로운 눈이 너무 샘나서 원숭이를 직접 패.. 2021. 7. 13. [백준] 이분탐색 - 2343번: 기타레슨 (Java) https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마.. 2021. 6. 15. [백준] 이분탐색 - 2805번 : 나무 자르기 (Java) https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱.. 2021. 6. 10. 이분탐색 이분탐색 (Binary Search) 수열(주어진 배열) 에서의 탐색 x가 존재하는지? x 이상, 이하, 등 의 원소는 몇개? 등의 조건을 탐색할 때의 시간복잡도 모두 O(N). 정렬된 수열에서의 탐색 -> 이분탐색 정렬이 보장되는 배열에서 기준원소를 가지고 범위를 이분하여 탐색 O(logN) 2021. 5. 25. 이전 1 2 다음
