이분탐색 (Binary Search)
이분탐색 알고리즘 참고:https://wootool.tistory.com/62
[알고리즘] 이분 탐색
이분 탐색 탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식입니다. 그렇기에 원래의 전부를 탐색하는 탐색 속도에 비해 빠릅니다. 이분 탐색을 하는 방법은 left , right , mid 값으로 탐..
wootool.tistory.com
이분탐색 알고리즘은 주어진 범위 내에서 구하고자 하는 값을 절반씩 줄여나가며 탐색하는 알고리즘이다.
따라서 탐색하는데 걸리는 시간은 1/2씩 좁혀나가므로 O(logN)이 된다.
알고리즘에 대한 상세한 설명은 문제와 소스코드를 분석하며 보자.
백준: 2805 나무자르기 https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따
www.acmicpc.net
나무의 갯수가 N개 주어지고 각각의 나무마다 높이가 1~10억 중 하나로 값이 정해져 있다. 그리고 모든 나무를 h만큼 자르면 나머지 윗부분을 가져갈 수 있다. 그래서 잘려진 나무들의 합이 M보다 크거나 같으면 나무를 가져갈 수 있고 그때 자른 크기 즉 h의 최댓값을 구하는 문제이다.
나무의 높이가 1~10억이므로 범위가 매우 커서 그냥 1부터 10억까지 h를 설정하며 일일이 탐색하기에는 시간초과가 발생하게 된다. 따라서 이렇게 범위가 주어졌을때 효과적으로 적용할 수 있는 탐색 알고리즘이 이분탐색이다. 처음 1을 hmin으로 주고 10억을 hmax 그리고 그 중간인 5억이 hmid값이 된다. 그리고 이때 hmid를 기준으로 잘려진 나무들의 윗부분의 합이 M보다 작으면 hmax=hmid-1이 되고 반대로 크면 hmin=hmid+1이 되어 범위를 절반씩 계속 줄여나갈 수 있다.
중요한것은 종료조건인데 while반복문을 (hmin<=hmax)로 하게 되면 계속해서 절반씩 자르다가 hmax=hmin인 지점이 반드시 오게되고 마지막에서 hmax=hmid-1; 또는 hmin=hmid+1연산을 하게되면 hmin,hmax값이 역전이 되어 반복문을 탈출 할 수 있다. 그리고 이 문제는 잘려진 나무들의 합이 M보다 큰 값들은 모두 가능한 h가 될 수 있어서 기존의 hmid일때의 나무들의 합이 M과 같게 되면 그때 h값을 저장할 수 있을 뿐만아니라 M이상이여도 h값을 가질 수 있다. 따라서 조건을 조금 변경하여
sum>=M일때 그중에서 h값을 비교를 통해 계속해서 갱신하면 된다.
소스코드