이분탐색 (Binary Search)

이분탐색 알고리즘 참고:https://wootool.tistory.com/62

[알고리즘] 이분 탐색

이분탐색 알고리즘은 주어진 범위 내에서 구하고자 하는 값을 절반씩 줄여나가며 탐색하는 알고리즘이다. 

따라서 탐색하는데 걸리는 시간은 1/2씩 좁혀나가므로 O(logN)이 된다.

 

알고리즘에 대한 상세한 설명은 문제와 소스코드를 분석하며 보자.

 

백준: 2805 나무자르기 https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

나무의 갯수가 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값을 비교를 통해 계속해서 갱신하면 된다.

 

 

소스코드