알고리즘/이분 탐색 썸네일형 리스트형 백준 2805번: 나무 자르기 (JAVA) 문제 해석 M미터의 나무가 필요하다. 높이 H를 지정하면 톱날이 H만큼 상승하고 자른 이후 (자르는 나무의 높이) - H 만큼의 나무를 얻을 수 있다. 필요 이상으로 얻지 않기 위해 M을 얻을 수 있게 하는 H 중 가장 큰 값을 최종 결과로 여긴다. 알고리즘 H를 나무들 중 가장 큰 높이로 지정한 후 원하는 결과가 나올 때까지 H를 줄여가며 원하는 결과가 나오면 반복을 종료하여 M만큼 얻을 수 있는 H의 최대 높이를 구하고자 하였다. 허나 다음과 같이 구현시 시간초과가 발생하였다. 따라서 결과를 좀 더 빨리 찾을 수 있도록 이분 탐색을 활용하였다. min은 0, max는 전과 같이 나무들 중 가장 큰 높이로 지정한다. 자르는 높이를 최소와 최대의 중간으로 하고 최소가 최대를 넘어서기 전까지 반복해서 자른.. 더보기 백준 2512번: 예산 (JAVA) <이분 탐색> 문제 해석 국가예산 총액 M 지방의 수 N 각 지방에서 요청하는 예산이 입력값으로 주어진다. M이 요청하는 예산을 다 수용할 수 있을만큼 크면 요청하는대로 예산을 분배해주지만 다 수용이 불가능하다면 상한선을 설정하여 상한액보다 큰 금액을 요청하는 지방에는 상한액을 배정하고 이외에는 요청하는대로 처리한다. 알고리즘 모든 경우를 다 찾아보려다 좀 아닌거 같아서 힌트를 참고하였는데 이 문제는 이분 탐색을 통해 원하는 값을 찾는 문제였다. 이분 탐색은 정렬되어 있는 리스트를 탐색 범위를 절반씩 좁혀가며 탐색하는 방법이다. 이분 탐색을 위해 이 문제에서는 left 변수를 0, right 변수를 요청액 중 가장 큰 값으로 설정하고 범위를 좁혀가며 적절한 값을 찾아가면 된다. 조건에 따라 left를 증가시키거나 ri.. 더보기 이전 1 다음
