![]()
🥕 [ 백준 2850 ] 나무 자르기 문제 링크 url : 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 만큼의 높이를 잘라 잘리는 부분 ( 주황색 ) 의 합이 M보다 크면 되는 문제이다. 나무의 갯수는 100만개 까지, 나무의 높이는 20억 까지 있다. 그리고 제한 시간은 1초이다. 주어진 input은 크면서 시간이 적기 때문에 문제 풀이로서 떠올릴 수 ..
[binary search] 정렬되어 있는 자료구조에서 중앙값의 크고 작음을 이용해서 데이터를 검색한다. 정렬되어 있지 않은 자료구조라면 먼저 정렬을 시켜 주어야 이진 탐색이 가능하다. 중앙값을 기준으로 검색 범위를 점차 좁혀나가는 방식이다. 다음과 같은 자료구조가 있다고 하자. [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] 이때 중앙값은 5 이다. 우리가 찾으려는 값을 2라고 한다면, 5보다 큰 값을 굳이 검색할 필요는 없을 것이다. [ 1, 2, 3, 4, 5 ] 여기서의 중앙값은 3이다. 따라서 4, 5는 필요가 없으므로 버려지게 된다. [ 1, 2, 3 ] 중앙값은 2 이다. 바로 내가 찾으려는 값이다. 반복문을 사용한 이진탐색 예시 코드 참조; 나동빈 (2020). . 서울시: 한빛미디어..
